PROBLEM LINK:Author: Ke Bi DIFFICULTY:EasyMedium 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 "walledoff" 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:
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".
asked 22 May '16, 22:03

The link to the codes are not working . Please fix it soon. answered 23 May '16, 00:19
