### PROBLEM LINK:

**Author:** Praveen Dhinwa

**Tester:** Mugurel Ionut Andreica

**Editorialist:** Praveen Dhinwa

### DIFFICULTY:

Easy

### PREREQUISITES:

breadth first search (bfs)

### PROBLEM:

You are given a n \times m size grid. Some of the cells of the grid are blocked. There are two robots one standing at (1, 1) and other at (n, m). In a single move, a robot can move from a cell (i, j) to cell (x, y) such that |x - i| + |y - j| \leq K, where K is fixed a constant (it can be different for robots, i.e. K_1, K_2). Both the robots make moves simultaneously, find out minimum number of moves required so that both the robots meet at some common cell. If it is not possible for them to meet, print -1.

### EXPLANATION:

**What if the grid was not blocked**

Note that if the grid would not have any blocked cells, then this turns into a greedy problem. Both the persons can make move greedily towards each other.

**With blocked grid cells**

Now, some of the grid cells might be blocked. You might think of finding whether there is a cell (i, j) which is reachable from both (1, 1) and (n, m) in exactly some i moves, where i can go up to n * m. You can check whether it is possible to reach cell (i, j) in k moves by a dp solution. Let dp(i, j, k) denote whether it is possible to reach cell (i, j) from cell (1, 1) or not. Note that dp(i, j, k) = min(dp((i, j, j), dp(x, y, k - 1) + 1, where |x - i| + |y - j| \leq K. Base case will be when k = 0, i.e. whether (i, j) is same cell as that of (1, 1) or not.

Unfortunately, this solution is quite slow. We need to think of something faster.

**An interesting observation**

Notice that the operations are in such a way that one can stay at its cell in an operation. Consider a cell (i, j), if the minimum number of steps required to reach cell (i, j) from (1, 1) be S_1 and that from (n, m) be S_2. Then, in max(S_1, S_2) steps, both the robots can meet at cell (i, j). It is simply due to the fact that the robot with the smaller distance to cell (i, j) will reach at the cell and will just stay their in its next remaining operations. The other robot will keep on moving meanwhile.

So, we need to find shortest distance of each robot to reach each cell (i, j). For that, we can do a bfs from cell (1, 1) and (n, m). The vertices of the graph will be all the cells of the grid. There will be an edge between two cells (i, j) and (x, y) of weight 1 if it is possible to reach from cell (i, j) to cell (x, y). Notice that if we can reach from cell (i, j) to cell (x, y) in a single step, then we reach from cell (x, y) to cell (i, j) in a single step too. This guarantees that our graph will be undirected. Finding shortest distance between a fixed node with other nodes in an unweighted (i.e. weight = 1) undirected graph can be done using breadth first search algorithm.

**Time Complexity**

Time complexity of breadth search algorithm is \mathcal{O} (V + E), where V denotes number of vertices and E denotes number of edges in the graph. In our graph, there are total \mathcal{O}(N * M) vertices. Number of edges in our graph will be \mathcal{O} (N * M * K * K).

So, overall time complexity will be \mathcal{O} (N * M * K_1 * K_2).