Medium

题目描述

给你一个 m x n 的二进制矩阵 grid 和一个整数 health。

你从左上角 (0, 0) 开始，想要到达右下角 (m - 1, n - 1)。

你可以向上、下、左、右移动到相邻的单元格，但你的健康值必须保持为正数。

单元格 (i, j) 如果 grid[i][j] = 1，则被认为是不安全的，会使你的健康值减少 1。

如果你能以 1 或更多的健康值到达最终单元格，返回 true，否则返回 false。

示例 1：

输入：grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1
输出：true
解释：可以沿着灰色单元格安全到达最终单元格。

示例 2：

输入：grid = [[0,1,1,0,0,0],[1,0,1,0,0,0],[0,1,1,1,0,1],[0,0,1,0,1,0]], health = 3
输出：false
解释：安全到达最终单元格至少需要 4 个健康点。

示例 3：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5
输出：true
解释：可以沿着灰色单元格安全到达最终单元格。任何不经过单元格 (1, 1) 的路径都是不安全的，因为到达最终单元格时健康值会降到 0。

约束条件：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • 2 <= m * n
  • 1 <= health <= m + n
  • grid[i][j] 是 0 或 1

提示：

  • 使用 01 BFS

解题思路

这是一个在带权图中寻找最短路径的问题。关键是理解每个格子的"权重"：安全格子权重为0，危险格子权重为1。我们需要找到从起点到终点的路径，使得总权重不超过 health-1。

解法分析

方法一：01-BFS（推荐） 由于边权只有0和1两种情况，可以使用01-BFS算法。这是一种特殊的BFS，使用双端队列：

  • 权重为0的边，将新状态加入队列头部
  • 权重为1的边，将新状态加入队列尾部

这样保证了队列中的状态按照距离递增排列，第一次到达终点时就是最优解。

方法二：Dijkstra算法 使用优先队列实现的Dijkstra算法也可以解决，但由于只有两种边权，01-BFS更高效。

方法三：动态规划 可以用DP记录到达每个位置的最小健康消耗，但空间复杂度较高。

实现要点

  1. 使用双端队列进行01-BFS
  2. 记录每个位置的最小健康消耗，避免重复访问
  3. 起始位置如果是危险格子，初始消耗为1
  4. 当到达终点时，检查剩余健康值是否≥1

代码实现

class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> cost(m, vector<int>(n, INT_MAX));
        deque<pair<int, int>> dq;
        
        int startCost = grid[0][0];
        cost[0][0] = startCost;
        dq.push_back({0, 0});
        
        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (!dq.empty()) {
            auto [x, y] = dq.front();
            dq.pop_front();
            
            for (auto& dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                
                int newCost = cost[x][y] + grid[nx][ny];
                if (newCost < cost[nx][ny]) {
                    cost[nx][ny] = newCost;
                    if (grid[nx][ny] == 0) {
                        dq.push_front({nx, ny});
                    } else {
                        dq.push_back({nx, ny});
                    }
                }
            }
        }
        
        return health - cost[m-1][n-1] >= 1;
    }
};

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        from collections import deque
        
        m, n = len(grid), len(grid[0])
        cost = [[float('inf')] * n for _ in range(m)]
        dq = deque()
        
        start_cost = grid[0][0]
        cost[0][0] = start_cost
        dq.append((0, 0))
        
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        while dq:
            x, y = dq.popleft()
            
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n:
                    new_cost = cost[x][y] + grid[nx][ny]
                    if new_cost < cost[nx][ny]:
                        cost[nx][ny] = new_cost
                        if grid[nx][ny] == 0:
                            dq.appendleft((nx, ny))
                        else:
                            dq.append((nx, ny))
        
        return health - cost[m-1][n-1] >= 1

public class Solution {
    public bool FindSafeWalk(IList<IList<int>> grid, int health) {
        int m = grid.Count, n = grid[0].Count;
        int[,] cost = new int[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                cost[i, j] = int.MaxValue;
            }
        }
        
        var dq = new LinkedList<(int, int)>();
        int startCost = grid[0][0];
        cost[0, 0] = startCost;
        dq.AddLast((0, 0));
        
        int[,] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        while (dq.Count > 0) {
            var (x, y) = dq.First.Value;
            dq.RemoveFirst();
            
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i, 0], ny = y + dirs[i, 1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
                
                int newCost = cost[x, y] + grid[nx][ny];
                if (newCost < cost[nx, ny]) {
                    cost[nx, ny] = newCost;
                    if (grid[nx][ny] == 0) {
                        dq.AddFirst((nx, ny));
                    } else {
                        dq.AddLast((nx, ny));
                    }
                }
            }
        }
        
        return health - cost[m-1, n-1] >= 1;
    }
}

var findSafeWalk = function(grid, health) {
    const m = grid.length;
    const n = grid[0].length;
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    
    const pq = [[0, 0, health - grid[0][0]]];
    const visited = new Set();
    
    while (pq.length > 0) {
        pq.sort((a, b) => b[2] - a[2]);
        const [row, col, hp] = pq.shift();
        
        if (hp <= 0) continue;
        
        if (row === m - 1 && col === n - 1) {
            return true;
        }
        
        const key = `${row},${col},${hp}`;
        if (visited.has(key)) continue;
        visited.add(key);
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n) {
                const newHp = hp - grid[newRow][newCol];
                const newKey = `${newRow},${newCol},${newHp}`;
                
                if (!visited.has(newKey) && newHp > 0) {
                    pq.push([newRow, newCol, newHp]);
                }
            }
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型01-BFS解法
时间复杂度O(mn)
空间复杂度O(mn)

说明：

  • 时间复杂度：每个格子最多被访问一次，总共mn个格子
  • 空间复杂度：需要存储每个位置的最小代价，以及双端队列的空间

相关题目