×

MAZE - Editorial

Author: Ke Bi
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza

Easy-Medium

PREREQUISITES:

BFS, DFS, Union find, dual graph

PROBLEM:

Given an $R\times C$ grid with $W$ coated walls between some pairs of adjacent cells, what is the minimum number of walls you have to coat so that the grid becomes disconnected?

QUICK EXPLANATION:

The answer can only be $2$, $1$, $0$, or "Chefland is doomed".

If $R\times C = 1$, the answer is "Chefland is doomed".

Consider the endpoints of coated walls as nodes of a graph, and the walls themselves as edges. Also, consider the boundary of the grid as a single node.

If there is a cycle in this graph, then the answer is $0$.

If you can add an edge which makes a cycle, the answer is $1$. This can be done efficiently using union find or BFS.

Otherwise, the answer is $2$.

EXPLANATION:

The only time that the grid can't be disconnected is when $R = C = 1$, which means there's only one bomb. Otherwise, regardless of the configuration, there's always a way to disconnect the grid using only $2$ coatings: simply coat off the walls of one of the corner bombs! (If some of those walls have already been coated, or if the grid has a width or height of $1$, then all the better; we will need less than $2$ coatings.) This gives us an upper bound of $2$ for the answer, and the only problem now is to figure out whether the answer is $2$, $1$ or $0$.

When is the answer $0$? This happens when the grid is already disconnected. So given a grid, how do you know if it's already disconnected? Note that we can't do a BFS/DFS on the grid because the grid can be very large. Instead, we take a look at some cases of disconnected grids:

What makes these disconnected is that there are "walled-off" sections of the grid. Such a section exists if and only if there is a cycle along the walls! See the following image:

More formally, if we consider the corners of the cells as "nodes" of a graph, and the walls themselves as the edges, then the answer is $0$ if and only if there is a cycle in this graph!

Now, you might say there is already a cycle all this time if you consider the boundary of the grid as walls:

But we don't consider that cycle. To do this in code, simply consider the whole boundary of the grid as a single node.

To find this cycle, we just construct this graph and perform a BFS/DFS on it. So now, we have a fast algorithm to compute whether the answer is $0$!

By the way, the graph we constructed is also known as the dual graph of the original graph, in the context of planar graphs.

But if the answer is not $0$, then the answer can only be $1$ or $2$ at this point, and we need to figure out which case it is. So when is the answer equal to $1$? The answer is $1$ if you can create a cycle along the walls by coating just one wall. For example, in the following images, we can coat one wall each to create a cycle:

So how do we code this? With BFS also! Here's one way:

• Perform a BFS on the dual graph, and remember the connected component of each node.
• For each node, try checking each of its four neighbors. If there's a neighbor in the same connected component but is not already adjacent to the current node, then the answer is $1$.
• If we can't find any, then the answer is $2$.

But be careful with implementation! If you implemented it like I mentioned above, where you turn the whole boundary of the grid into a single node, then it's possible you might get the following case wrong:

To guard against this test case, just remember the original walls as given in the input.

Another possible case you might get wrong is the following:

In this case, the answer is $1$ because you can coat any vertical wall to disconnect the graph, even though the boundary is represented as a single node.

So now we have an algorithm that runs in $O(W \log W)$ time (because of the usage of maps/sets)! As a final note, you can also use union find to implement the things we described above.

Time Complexity:

$O(W \log W)$

AUTHOR'S AND TESTER'S SOLUTIONS:

This question is marked "community wiki".

1.7k480138
accept rate: 11%

 0 The link to the codes are not working . Please fix it soon. answered 23 May '16, 00:19 3★dhopal 1 accept rate: 0% I think it's fixed now. (23 May '16, 01:13)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×13,419
×1,201
×537
×375
×91
×61
×11

question asked: 22 May '16, 22:03

question was seen: 2,916 times

last updated: 23 May '16, 22:50