BackTrackingProblem 11 of 19

Find shortest safe route in a path with landmines

Brute Force
Time: O(2^(m×n))
Space: O(m×n)
Optimal
Time: O(m×n)
Space: O(m×n)

Problem Statement

Given a matrix representing a minefield where 0 denotes a landmine and 1 denotes a safe cell. A cell adjacent (up, down, left, right) to a landmine is also unsafe. Find the shortest safe route from any cell in the first column to any cell in the last column. A route can only traverse safe cells.

Example:

Input: matrix = [ [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 0, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 0, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 0, 1, 1, 1, 1], [1, 0, 1, 1, 1, 1, 1, 1, 0, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] ] Output: Length of shortest safe route is 13 Explanation: Path avoiding all mines and adjacent cells.

Approach 1: Brute Force (Backtracking)

Intuition

First mark all unsafe cells (landmines and their adjacent cells). Then use backtracking to try all paths from first column to last column, tracking the minimum length.

Algorithm

  1. Mark unsafe cells (landmines and neighbors)
  2. Try starting from each safe cell in first column
  3. Use backtracking to explore all paths
  4. Track minimum path length
java
import java.util.*;

class Solution {
    private int[] dr = {-1, 0, 1, 0};
    private int[] dc = {0, 1, 0, -1};
    private int minDist;
    
    public void markUnsafe(int[][] mat, int row, int col, int m, int n) {
        for (int i = 0; i < 4; i++) {
            int r = row + dr[i];
            int c = col + dc[i];
            if (r >= 0 && r < m && c >= 0 && c < n && mat[r][c] != 0) {
                mat[r][c] = -1;
            }
        }
    }
    
    public void findPath(int[][] mat, int row, int col, int m, int n,
                         int dist, boolean[][] visited) {
        if (col == n - 1) {
            minDist = Math.min(minDist, dist);
            return;
        }
        
        if (dist >= minDist) return;
        
        visited[row][col] = true;
        
        for (int i = 0; i < 4; i++) {
            int newRow = row + dr[i];
            int newCol = col + dc[i];
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                mat[newRow][newCol] == 1 && !visited[newRow][newCol]) {
                findPath(mat, newRow, newCol, m, n, dist + 1, visited);
            }
        }
        
        visited[row][col] = false;
    }
    
    public int shortestPath(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    markUnsafe(mat, i, j, m, n);
                }
            }
        }
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == -1) mat[i][j] = 0;
            }
        }
        
        minDist = Integer.MAX_VALUE;
        boolean[][] visited = new boolean[m][n];
        
        for (int i = 0; i < m; i++) {
            if (mat[i][0] == 1) {
                findPath(mat, i, 0, m, n, 0, visited);
            }
        }
        
        return minDist == Integer.MAX_VALUE ? -1 : minDist;
    }
}

Complexity Analysis

  • Time Complexity: O(2^(m×n)) - Exponential in worst case
  • Space Complexity: O(m×n) - Visited array and recursion stack

Approach 2: Optimal (BFS)

Intuition

BFS naturally finds shortest path in unweighted graphs. Use multi-source BFS starting from all safe cells in first column.

Algorithm

  1. Mark unsafe cells
  2. Add all safe cells in first column to queue
  3. BFS level by level
  4. First time we reach last column is shortest path
java
import java.util.*;

class Solution {
    public int shortestPath(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[] dr = {-1, 0, 1, 0};
        int[] dc = {0, 1, 0, -1};
        
        // Mark cells adjacent to landmines
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    for (int k = 0; k < 4; k++) {
                        int r = i + dr[k];
                        int c = j + dc[k];
                        if (r >= 0 && r < m && c >= 0 && c < n && mat[r][c] != 0) {
                            mat[r][c] = -1;
                        }
                    }
                }
            }
        }
        
        // BFS
        Queue<int[]> queue = new LinkedList<>();
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, -1);
        
        // Add all safe cells in first column
        for (int i = 0; i < m; i++) {
            if (mat[i][0] == 1) {
                queue.offer(new int[]{i, 0});
                dist[i][0] = 0;
            }
        }
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int row = curr[0], col = curr[1];
            
            // Reached last column
            if (col == n - 1) {
                return dist[row][col];
            }
            
            for (int i = 0; i < 4; i++) {
                int newRow = row + dr[i];
                int newCol = col + dc[i];
                
                if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n &&
                    mat[newRow][newCol] == 1 && dist[newRow][newCol] == -1) {
                    dist[newRow][newCol] = dist[row][col] + 1;
                    queue.offer(new int[]{newRow, newCol});
                }
            }
        }
        
        return -1;
    }
}

Complexity Analysis

  • Time Complexity: O(m×n) - Each cell visited once
  • Space Complexity: O(m×n) - Queue and distance array

Key Takeaways

  1. Pre-processing: Mark unsafe adjacent cells before pathfinding
  2. Multi-source BFS: Start from all valid starting points simultaneously
  3. BFS for Shortest Path: BFS guarantees shortest path in unweighted graph
  4. 4-directional Movement: Up, down, left, right moves only
  5. Edge Cases: No safe path exists, first/last column all unsafe
  6. Real-world Application: Robot navigation, game pathfinding
Previous
Tug of War
Next
Combinational Sum