Shortest Safe Route In A Field With Landmines

• 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).

O(3^(M*N)), where ‘M’ represents the number of rows in the field and ‘N’ represents the number of columns in the field.

Marking the unsafe nodes as 0 requires O(M*N) time. Also, in the worst case, we make three recursive calls for every cell in the field. As there are M*N cells, hence it requires O(3^(M*N)). So, the overall time complexity is O(M*N + 3^(M*N)) = O(3^(M*N))

O(M*N), where ‘M’ represents the number of rows in the field and ‘N’ represents the number of columns in the field.

Extra space is required for the recursion stack. In the worst case, the depth of the recursion stack can be of order O(M*N). Hence, the overall space complexity is O(M*N).