LeetCode 解題筆記：3286. Find a Safe Walk Through a Grid

作者：王一哲
日期：2026年7月2日


LeetCode 題目連結：3286. Find a Safe Walk Through a Grid

解題想法

中等難度題。題目給定代表地圖的二維陣列 $grid$，假設尺寸為 $m \times n$，地圖中的數字代表走到這格會扣的血量，題目要求從左上角 $(0, 0)$ 出發走到右下角 $(m-1, n-1)$，如果能夠走到右下角回傳 True，如果無法走到右下角回傳 False。這類走格子的題目，我習慣用 BFS 解題。用 $que$ 儲存待走訪的格子座標，另外再開一個二維陣列 $visited$，用來儲存走到這格的最大血量，預設值為 $-1$，代表還沒有走到這格。持續從 $que$ 之中取出目前檢查的格子座標 $(r, c)$，如果 $r = m-1, c = n-1$ 回傳 True，如果還沒有走到終點則要做四方位檢查。時間複雜度為 $O(n^2)$。

Python 程式碼

Runtime: 63 ms, beats 83.49%. Memory: 19.47 MB, beats 97.17%.

class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])  # 地圖尺寸 m*n
        visited = [[-1] * n for _ in range(m)]  # 是否已走訪，-1 代表未走訪
        visited[0][0] = health - grid[0][0]  # 正值代表走到這格的 hp，起點可能會扣血
        que = deque([(0, 0)])  # 待走訪佇列
        # --- BFS ---
        while que:
            r, c = que.popleft()  # 目前的位置
            curr = visited[r][c]  # 目前的血量
            if r == m-1 and c == n-1:  # 走到終點，回傳 True
                return True
            # 四方位檢查
            for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
                nr, nc = r + dr, c + dc
                # 如果 (nr, nc) 未出界，目前的血量大於 (nr, nc) 會扣的血量，剩下的血量大於之前走到 (nr, nc) 的血量
                if 0 <= nr < m and 0 <= nc < n and curr > grid[nr][nc] and curr - grid[nr][nc] > visited[nr][nc]:
                    visited[nr][nc] = curr - grid[nr][nc]
                    que.append((nr, nc))
        return False

C++ 程式碼

Runtime: 10 ms, beats 84.59%. Memory: 31.75 MB, beats 61.33%.

class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int m = (int)grid.size(), n = (int)grid[0].size();  // 地圖尺寸 m*n
        int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0};
        vector<vector<int>> visited (m, vector<int> (n, -1));  // 是否已走訪，-1 代表未走訪
        visited[0][0] = health - grid[0][0];  // 正值代表走到這格的 hp，起點可能會扣血
        queue<pair<int, int>> que;  // 待走訪佇列
        que.push({0, 0});
        /* BFS */
        while(!que.empty()) {
            int r = que.front().first, c = que.front().second;  // 目前的位置
            que.pop();
            int curr = visited[r][c];  // 目前的血量
            if (r == m-1 && c == n-1) {  // 走到終點，回傳 True
                return true;
            }
            // 四方位檢查
            for(int i = 0; i < 4; i++) {
                int nr = r + dr[i], nc = c + dc[i];
                // 如果 (nr, nc) 未出界，目前的血量大於 (nr, nc) 會扣的血量，剩下的血量大於之前走到 (nr, nc) 的血量
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && curr > grid[nr][nc] && curr - grid[nr][nc] > visited[nr][nc]) {
                    visited[nr][nc] = curr - grid[nr][nc];
                    que.push({nr, nc});
                }
            }
        }
        return false;
    }
};