Leetcode网格消障最短路径问题：回溯法遇TLE求优化方案

Hey there! Let's break down why your backtracking approach is timing out and how to optimize it to handle larger grids efficiently.

Why Your Backtracking Solution Fails for Large Grids #

Backtracking works by exploring every possible path, which leads to an exponential time complexity—great for tiny grids, but way too slow when the grid scales up. The biggest flaws here are:

• You're revisiting the same cells repeatedly (like moving right then looping back left) without any check if a prior visit to that cell was in a better state.
• No pruning for redundant states: If you reach (x,y) with 2 obstacle eliminations left in 5 steps, there's zero reason to process a later visit to (x,y) with only 1 elimination left in 6 steps—the first state is strictly better.

The Optimal Approach: BFS + State Tracking #

Breadth-First Search (BFS) is perfect for shortest path problems because it explores paths level by level (each level equals one step count). The first time you hit the end cell, you know that's the shortest path. To avoid wasted work, we'll track the maximum number of obstacle eliminations remaining when we visit each cell—this lets us skip any worse states that come later.

Key Details: #

• Queue State: Each element in the queue stores (x, y, remainingK, steps)—current position, how many obstacles we can still eliminate, and steps taken so far.
• Visited Tracking: Use a 2D array visited[x][y] where we store the maximum number of obstacle eliminations we had left when visiting (x,y). If we later reach (x,y) with fewer or equal remaining eliminations than what's recorded, we skip this state (since the prior visit was better).

Optimized Java Code #

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int shortestPath(int[][] grid, int k) {
        int m = grid.length;
        int n = grid[0].length;
        
        // Quick win: if k is large enough to clear all obstacles in the shortest path
        if (k >= m + n - 2) {
            return m + n - 2;
        }
        
        // Directions: up, down, left, right
        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        // visited[x][y] = max remaining k when we visited (x,y)
        int[][] visited = new int[m][n];
        // Initialize all to -1 (unvisited)
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                visited[i][j] = -1;
            }
        }
        
        Queue<int[]> queue = new LinkedList<>();
        // Start at (0,0) with k eliminations left, 0 steps
        queue.add(new int[]{0, 0, k, 0});
        visited[0][0] = k;
        
        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int x = curr[0];
            int y = curr[1];
            int remainingK = curr[2];
            int steps = curr[3];
            
            // Check if we've reached the end
            if (x == m - 1 && y == n - 1) {
                return steps;
            }
            
            // Explore all four directions
            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                // Check if new position is within grid bounds
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newRemainingK = remainingK;
                    // If it's an obstacle, use one elimination
                    if (grid[nx][ny] == 1) {
                        newRemainingK--;
                    }
                    
                    // Only process this state if:
                    // 1. We still have eliminations left
                    // 2. This state is better than any previous visit to (nx, ny)
                    if (newRemainingK >= 0 && visited[nx][ny] < newRemainingK) {
                        visited[nx][ny] = newRemainingK;
                        queue.add(new int[]{nx, ny, newRemainingK, steps + 1});
                    }
                }
            }
        }
        
        // If loop ends without returning, end is unreachable
        return -1;
    }
}

Code Explanation: #

1. Edge Case Handling: If k is larger than or equal to m+n-2 (the maximum number of obstacles we could hit on the shortest path from start to end), we can immediately return the shortest path length—we can clear every obstacle in the way.
2. Visited Array: A 2D array (instead of a 3D one) tracks the maximum remaining eliminations for each cell, saving space while efficiently pruning redundant states.
3. BFS Loop: For each cell, we explore all four directions. If moving to a cell requires using an elimination (it's an obstacle), we decrement remainingK. We only add the new state to the queue if it's better than any prior visit to that cell (more remaining eliminations).

Why This Works #

BFS guarantees that the first time we reach the end cell, it's via the shortest path. The visited tracking ensures we never process a state that's worse than a previous one—this cuts down on unnecessary computations drastically, making the solution efficient enough for large grids.

内容的提问来源于stack exchange，提问作者Amit Biswas