PROBLEM LINK:
Author: Misha Chorniy
Tester: Karan Aggarwal
Editorialist: Pushkar Mishra
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Breadth First Search, Graphs
PROBLEM:
Given is a matrix of dimensions N\times M in which some cells are marked with “.”, some with “", and one with “C”. The “.” indicates that the cell can be visited, "” denotes restricted cell and “C” denotes the capital city. We have to give a sequence of moves of length at max 10^5 in terms of “L” (left), “R” (right), “U” (up) and “D” (down) such that a robot starting from any “.” cell in the in the grid and following the sequence of moves visits the “C” cell at least once.
EXPLANATION:
This problem doesn’t require much thinking beyond the brute force way to do it. However, it is implementation heavy.
It is given that our matrix can at maximum be of 20 \times 20 cells. This clearly hints towards the algorithm being close to brute force. Let us think about all the “.” cells one by one. To begin with, let us look at the farthest “.” cell from the capital city. How far can it be from the capital city? It is given that all the border cells are “*”. This means that there can be a maximum of 400 - (20 - 20 -18 - 18) = 324 cells at maximum which are “.” marked.
This tells us that the shortest path from any “.” cell to capital city is at max 324 instructions (instructions being “L”, “R”, “U”, “D”) long. We first make a string of moves for the cell “.” that is farthest from the capital city. For all other “.” cells, we will have to execute the the same moves as well. After all the commands are executed, the farthest one has reached the capital city, and the others are in some position in the grid (most likely, not in the position they were).
Then we pick another one, and make it reach the capital city. The sequence of moves it takes for this is appended to the string we had from before, and all the remaining “.” cells are again moved accordingly. We continue doing this for each of the “.” cells till we have made each of them reach the capital city.
What is the length of the string at the end of all these operations? We have to move at most 324 cells. As we calculated before, the maximum length for one movement is 324 again. So, in total, 324*324 = 104976. This is slightly more than 10^5. How do reduce this to below 10^5? Actually, if we reason a bit more, we will see that the shortest path from any place in the grid to the capital city is 324 in theory only; it is actually much less. This is because 324 will only be if during a path from a cell to the capital, one has to go over all other cells. But why would one do that? We can move in all directions, so we can simply go from one row to its neighbouring ones or one column to its neighbouring ones. This tells us that the path will definitely be much shorter, definitely shorter than something like 305. And 305 * 324 = 98820. This is less than 10^5. So this works.
But what is the time complexity? For each of the “.” cells, we need to first do a BFS to find the shortest move sequence to the capital city. Then, for all the remaining “.” cells, we need to make them follow the same move sequence. There can be \mathcal{O}(NM) cells of type “.”. BFS takes \mathcal{O}(NM). But moving all other “.” cells on the same move sequence takes \mathcal{O}(N^2M^2); hence, this is the costliest operation per “.” cell. So the total complexity is \mathcal{O}(N^3M^3). This is sufficient given that N = M = 20 in the maximum case.
Please see setter’s/tester’s program for implementation details.
COMPLEXITY:
\mathcal{O}(N^3M^3)
??