Skip to content

3286. Find a Safe Walk Through a Grid

Description

You are given an m x n binary matrix grid and an integer health.

You start on the upper-left corner (0, 0) and would like to get to the lower-right corner (m - 1, n - 1).

You can move up, down, left, or right from one cell to another adjacent cell as long as your health remains positive.

Cells (i, j) with grid[i][j] = 1 are considered unsafe and reduce your health by 1.

Return true if you can reach the final cell with a health value of 1 or more, and false otherwise.

 

Example 1:

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]], health = 1

Output: true

Explanation:

The final cell can be reached safely by walking along the gray cells below.

Example 2:

Input: 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

Output: false

Explanation:

A minimum of 4 health points is needed to reach the final cell safely.

Example 3:

Input: grid = [[1,1,1],[1,0,1],[1,1,1]], health = 5

Output: true

Explanation:

The final cell can be reached safely by walking along the gray cells below.

Any path that does not go through the cell (1, 1) is unsafe since your health will drop to 0 when reaching the final cell.

 

Constraints:

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

Solutions

Solution 1: BFS

Thinking

A \(1\)-cell costs one health; we must reach the end with health left. \(m,n\le 50\). A visited-only BFS is not enough, because a cheaper path may arrive later.

\(dist[i][j]\) is the least cost to that cell; a successful relaxation enqueues. Weights are \(0/1\), so the queue BFS is valid. The end is safe iff that cost is strictly below \(\textit{health}\).

We define a 2D array \(\textit{dist}\), where \(\textit{dist}[i][j]\) represents the minimum health value required to reach position \((i, j)\) from the top-left corner. Initially, we set \(\textit{dist}[0][0]\) to \(\textit{grid}[0][0]\) and add \((0, 0)\) to the queue \(\textit{q}\).

Then, we continuously take elements \((x, y)\) from the queue and try to move in four directions. If we move to a valid position \((nx, ny)\) and the health value required to move from \((x, y)\) to \((nx, ny)\) is smaller, we update \(\textit{dist}[nx][ny] = \textit{dist}[x][y] + \textit{grid}[nx][ny]\) and add \((nx, ny)\) to the queue \(\textit{q}\).

Finally, when the queue is empty, we obtain \(\textit{dist}[m-1][n-1]\), which is the minimum health value required to reach the bottom-right corner from the top-left corner. If this value is less than \(\textit{health}\), then we can reach the bottom-right corner; otherwise, we cannot.

The time complexity is \(O(m \times n)\), and the space complexity is \(O(m \times n)\). Here, \(m\) and \(n\) are the number of rows and columns of the grid, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
        m, n = len(grid), len(grid[0])
        dist = [[inf] * n for _ in range(m)]
        dist[0][0] = grid[0][0]
        q = deque([(0, 0)])
        dirs = (-1, 0, 1, 0, -1)
        while q:
            x, y = q.popleft()
            for a, b in pairwise(dirs):
                nx, ny = x + a, y + b
                if (
                    0 <= nx < m
                    and 0 <= ny < n
                    and dist[nx][ny] > dist[x][y] + grid[nx][ny]
                ):
                    dist[nx][ny] = dist[x][y] + grid[nx][ny]
                    q.append((nx, ny))
        return dist[-1][-1] < health

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
        int m = grid.size();
        int n = grid.get(0).size();
        int[][] dist = new int[m][n];
        for (int[] row : dist) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        dist[0][0] = grid.get(0).get(0);
        Deque<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {0, 0});
        final int[] dirs = {-1, 0, 1, 0, -1};
        while (!q.isEmpty()) {
            int[] curr = q.poll();
            int x = curr[0], y = curr[1];
            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i];
                int ny = y + dirs[i + 1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n
                    && dist[nx][ny] > dist[x][y] + grid.get(nx).get(ny)) {
                    dist[nx][ny] = dist[x][y] + grid.get(nx).get(ny);
                    q.offer(new int[] {nx, ny});
                }
            }
        }
        return dist[m - 1][n - 1] < health;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    bool findSafeWalk(vector<vector<int>>& grid, int health) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        dist[0][0] = grid[0][0];
        queue<pair<int, int>> q;
        q.emplace(0, 0);
        int dirs[5] = {-1, 0, 1, 0, -1};
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x + dirs[i];
                int ny = y + dirs[i + 1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] > dist[x][y] + grid[nx][ny]) {
                    dist[nx][ny] = dist[x][y] + grid[nx][ny];
                    q.emplace(nx, ny);
                }
            }
        }
        return dist[m - 1][n - 1] < health;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func findSafeWalk(grid [][]int, health int) bool {
    m, n := len(grid), len(grid[0])
    dist := make([][]int, m)
    for i := range dist {
        dist[i] = make([]int, n)
        for j := range dist[i] {
            dist[i][j] = math.MaxInt32
        }
    }
    dist[0][0] = grid[0][0]
    q := [][2]int{{0, 0}}
    dirs := []int{-1, 0, 1, 0, -1}
    for len(q) > 0 {
        curr := q[0]
        q = q[1:]
        x, y := curr[0], curr[1]
        for i := 0; i < 4; i++ {
            nx, ny := x+dirs[i], y+dirs[i+1]
            if nx >= 0 && nx < m && ny >= 0 && ny < n && dist[nx][ny] > dist[x][y]+grid[nx][ny] {
                dist[nx][ny] = dist[x][y] + grid[nx][ny]
                q = append(q, [2]int{nx, ny})
            }
        }
    }
    return dist[m-1][n-1] < health
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
function findSafeWalk(grid: number[][], health: number): boolean {
    const m = grid.length;
    const n = grid[0].length;
    const dist: number[][] = Array.from({ length: m }, () => Array(n).fill(Infinity));
    dist[0][0] = grid[0][0];
    const q: [number, number][] = [[0, 0]];
    const dirs = [-1, 0, 1, 0, -1];
    while (q.length > 0) {
        const [x, y] = q.shift()!;
        for (let i = 0; i < 4; i++) {
            const nx = x + dirs[i];
            const ny = y + dirs[i + 1];
            if (
                nx >= 0 &&
                nx < m &&
                ny >= 0 &&
                ny < n &&
                dist[nx][ny] > dist[x][y] + grid[nx][ny]
            ) {
                dist[nx][ny] = dist[x][y] + grid[nx][ny];
                q.push([nx, ny]);
            }
        }
    }
    return dist[m - 1][n - 1] < health;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
impl Solution {
    pub fn find_safe_walk(grid: Vec<Vec<i32>>, health: i32) -> bool {
        let m = grid.len();
        let n = grid[0].len();
        let inf: i32 = i32::MAX / 2;

        let mut dist = vec![vec![inf; n]; m];
        dist[0][0] = grid[0][0];

        let mut q = std::collections::VecDeque::new();
        q.push_back((0usize, 0usize));

        let dirs = [(-1i32, 0i32), (1, 0), (0, -1), (0, 1)];

        while let Some((x, y)) = q.pop_front() {
            for (dx, dy) in dirs {
                let nx = x as i32 + dx;
                let ny = y as i32 + dy;

                if nx >= 0 && nx < m as i32 && ny >= 0 && ny < n as i32 {
                    let nx = nx as usize;
                    let ny = ny as usize;

                    let new_cost = dist[x][y] + grid[nx][ny];
                    if new_cost < dist[nx][ny] {
                        dist[nx][ny] = new_cost;
                        q.push_back((nx, ny));
                    }
                }
            }
        }

        dist[m - 1][n - 1] < health
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class Solution {
    public bool FindSafeWalk(IList<IList<int>> grid, int health) {
        int m = grid.Count;
        int n = grid[0].Count;
        int inf = int.MaxValue / 2;

        int[,] dist = new int[m, n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dist[i, j] = inf;
            }
        }

        dist[0, 0] = grid[0][0];

        var q = new Queue<(int x, int y)>();
        q.Enqueue((0, 0));

        int[] dirs = new int[] { -1, 0, 1, 0, -1 };

        while (q.Count > 0) {
            var (x, y) = q.Dequeue();

            for (int i = 0; i < 4; i++) {
                int nx = x + dirs[i];
                int ny = y + dirs[i + 1];

                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int newCost = dist[x, y] + grid[nx][ny];
                    if (newCost < dist[nx, ny]) {
                        dist[nx, ny] = newCost;
                        q.Enqueue((nx, ny));
                    }
                }
            }
        }

        return dist[m - 1, n - 1] < health;
    }
}

Comments