Last Updated: 10 Feb, 2021
Shortest Safe Route In A Field With Landmines
Moderate
Asked in companies
Recently Ninja has been learning about a new Ninja Technique to cross a field with landmines. The field is in the form of a rectangular matrix of size M x N, having few landmines, which are placed arbitrarily. The landmine gets triggered if a person is any closer than one cell from the position where it is placed. So Ninja must avoid the landmines and any of the four adjacent cells (left, right, above and below), as they are also unsafe.
Initially Ninja is on one side of the field and has to move to the other side. You need to help Ninja apply the new Ninja Technique by providing him with the length of the shortest safe route possible from any cell in the first column to any cell in the last column of the field.
Note that Ninja is only allowed to move only in the direction left, right, above and below i.e., he cannot move diagonally to the next cell.
Note :
The length of the path is the number of steps required to reach from the first column of the field to the last column i.e., one less than the number of cells in the path.
For Example :
Consider the field of size 4*4, shown below. The cells containing landmine are marked with 0 and red colour. The cells near the landmine which are unsafe are marked with a light red colour.
The shortest safe route for Ninja, starting from any cell in the first column to any cell in the last column of the field is marked with green colour. The length of the path is 3.
Input Format :
The very first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of every test case contains two space-separated integers ‘M’ and ‘N’ denoting the number of rows and columns, respectively, in the field matrix.
The next 'M' lines of the input contain 'N' space-separated integers - 0 or 1, where 0 denotes the presence of landmine at that cell and 1 denotes the absence of landmine.
Output Format :
For each test case, print the length of the shortest safe route possible from any cell in the first column to any cell in the last column of the field. In case no such path exists, print -1.
Print the output of each test case in a separate line.
Note :
You do not need to print anything, it has already been taken care of. Just return the length of the shortest path.
Constraints :
1 <= T <= 10
1 <= N, M <= 1000
0 <= Field[i][j] <= 1
Time Limit: 1 sec
Approaches
- A brute force approach could be to generate all the possible paths from the first column of the field to the last column and choose the one with the shortest length.
- The idea is to use the concept of backtracking.
- Firstly we mark all the unsafe cells as 0 which are 1. This is done so as to avoid generating paths passing through an unsafe cell.
- Then for each safe cell in the first column, we generate the path starting from that cell by recursively moving in all the possible directions (left, right, above, and below). Also, keeping in mind not to include the cells which have been marked as zero.
- While generating the path we keep track of which cells have already been visited so that we do not move to the same cell. We also keep track of the length of the path generated so far.
- If a path through the current cell leads to a safe cell in the last column of the field, we update the shortest path length which we have found so far.
- Otherwise, we mark the current cell as unvisited and backtrack to the previous cell.
- In case there is no such path that leads to a safe cell in the last column of the field, we return -1.
Algorithm
- Firstly we mark all the unsafe cells of the field as 0.
- Create a variable, say minLength, to store the length of the shortest path found so far and initialise it to infinity.
- For all the safe cells in the first column of the matrix:
- Mark all the cells in the visited array as unvisited.
- Call the function shortestPathHelper on the current cell as shortestPathHelper(field, visited, i, j, minLength, 0).
- If minLength= N-1, break from the loop as there can be no other path with a shorter length.
- If minLength = infinity, there is no such path that leads to a safe cell in the last column of the field. So, we return -1.
- Otherwise, return minLength.
Algorithm for ‘shortestPathHelper’ function
- The function shortestPathHelper(field, visited, i, j, minLength, curLength) takes the given field matrix, visited matrix, row index of the current cell, column index of the current cell, length of the shortest path found so far, and length of the path generated so far, respectively, as its arguments.
- Base Condition 1: If j == N-1, we have generated a valid path. So, update the minLength, if required i.e. minLength = MIN(minLength, curLength) and return.
- Base Condition 2: If curLength >= minLength, the path being generated is longer than the shortest path found so far. So, no need to update minLength, just return.
- Mark the current cell as visited.
- For each of the adjacent cells (left, right, above and below):
- If the cell is safe (i.e. field[i][j] = 1) and not visited before, then add it to the current path by recursively calling the function shortestPathHelper(field, visited, x, y, minLength, curLength + 1), where x and y are the row and column index of the cell.
- Mark the current cell as unvisited and return (backtracking to the previous cell).
- This approach is similar to the previous approach.
- The idea is to traverse the field using BFS instead of using recursion.
- Firstly we mark all the unsafe cells as 0 which are 1. This is done so as to avoid generating paths passing through an unsafe cell.
- Now, push all the safe cells, present in the first column, into the queue and apply BFS.
- During the traversal, we keep track of which cells have already been visited so that we do not move to the same cell.
- We also keep track of the length of the path required to reach the current cell, by storing this length in a matrix.
- If we reach a safe cell in the last column, then we have found the shortest path.
- In case there is no such path that leads to a safe cell in the last column of the field, we return -1.
Algorithm
- Firstly we mark all the unsafe cells of the field as 0.
- Create a matrix dist of size M*N and initialise all the cells to -1. Here, dist[i][j] stores the length of the shortest path ending at cell (i, j).
- Create an empty queue which can hold coordinates of a cell.
- Initialise the queue by pushing the coordinates of all the safe cells, present in the first column. Also, set their distance values as 0.
- Repeat the following steps until the queue becomes empty:
- Pop the top coordinates from the queue. This will be the current cell which we will be exploring.
- Let i and j be the row and column index of the current cell.
- If the current cell is present in the last column, then return its distance i.e. dist[i][j].
- For each of the adjacent cells (left, right, above and below):
- Let x and y be the row and column index of the cell.
- If the cell is safe (i.e. field[i][j] = 1) and not visited before (i.e. dist[x][y] = -1), update its distance as dist[x][y] = dist[i][j] + 1.
- Push the coordinates of the cell into the queue.
- No valid path is found. So, return -1.