PROBLEM LINK:
Author: Ke Bi
Tester: Kevin Atienza
Translators: Vasya Antoniuk (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Kevin Atienza
DIFFICULTY:
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)