3286. Find a Safe Walk Through a Grid

MediumBreadth-First SearchGraphArrayMatrixShortest PathHeap (Priority Queue)

Problem Description

You are given an m x n binary matrix grid and an integer health. You begin your journey at the upper-left corner (0, 0) and aim to reach the lower-right corner (m - 1, n - 1). Movement is possible in four directions: up, down, left, or right to an adjacent cell, provided your health stays positive. Cells marked as 1 in the matrix are deemed unsafe and will deduct 1 from your health upon engaging with them. Your goal is to determine if you can reach the final cell with a minimum health value of 1 or more. If possible, return true; otherwise, return false.

Intuition

The essence of this problem rests in navigating a grid-like matrix while maintaining positive health. The approach we take is akin to finding the shortest path in an unweighted graph but with a constraint: our health acts as a diminishing resource as we move through unsafe cells.

The solution utilizes a Breadth-First Search (BFS) strategy to systematically explore all potential paths from the start to the end of the grid. We maintain a 2D array dist where each cell holds the minimum health cost to arrive at that cell from the starting point (0, 0). Initially, dist[0][0] is set to grid[0][0], and the starting cell is added to a queue for processing.

As we process each cell, we explore all four possible movements (up, down, left, right) to adjacent cells. If traversing to a neighbouring cell results in a lower health cost than previously recorded, we update dist for that cell and append it to the queue for further exploration.

Once the queue is exhausted, dist[m-1][n-1] reflects the minimal health expenditure to reach the destination. If this cost is below health, reaching the bottom-right corner with non-negative health is achievable, hence returning true; otherwise, it is not feasible, hence returning false.

Learn more about Breadth-First Search, Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

To tackle the problem, we employ the Breadth-First Search (BFS) algorithm, which is suitable due to its level-order exploration of nodes, aligning well with the requirement to find a minimum path cost. Here's a breakdown of the implementation:

Initialization:
- Define a 2D array dist, representing the minimum health cost required to reach each cell from the top-left corner. Initially, each cell is set to infinity, inf, to denote that it has not been visited or calculated.
- Set dist[0][0] to grid[0][0] since the journey begins at the starting cell.
- Use a queue q to manage our processing of cells, initialized with the starting cell (0, 0).
- Define dirs as a tuple (-1, 0, 1, 0, -1) to help navigate up, down, left, and right directions conveniently.
BFS Iteration:
- Execute a loop while the queue q is not empty, which means there are still cells to process.
- Dequeue the front cell (x, y), examining each direction using consecutive entries from dirs to compute the next cell coordinates (nx, ny).
Health Cost Update:
- For each valid neighboring cell (nx, ny), check if moving from (x, y) to (nx, ny) yields a lower health cost than currently recorded in dist[nx][ny].
- If so, update dist[nx][ny] with this new cost, and enqueue (nx, ny) for subsequent exploration.
Check Target:
- After BFS completion, dist[m-1][n-1] indicates the minimum health cost to reach the bottom-right corner. If this cost is less than the provided health, return true, signifying a successful path; otherwise, return false.

This efficient use of BFS ensures that all potential paths are explored and the optimal path is determined based on health constraints.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a simple grid example to illustrate the solution approach:

grid = [
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0]
]
health = 3

Given this 3x3 grid and an initial health of 3, the task is to determine whether it's possible to reach the bottom-right corner (2, 2) with at least a health value of 1.

Initialization:
- Create a 2D array dist initialized as follows:
```
dist = [
  [inf, inf, inf],
  [inf, inf, inf],
  [inf, inf, inf]
]
```
- Set dist[0][0] to grid[0][0], which is 0, indicating no health deduction at the starting point.
- Initialize a queue q with (0, 0), the starting cell.
- Define dirs as [(1, 0), (0, 1), (-1, 0), (0, -1)] to facilitate navigation.
BFS Iteration:
- Dequeue (0, 0) from the queue. Check its neighbors:
  - (1, 0) is a valid neighbor. grid[1][0] is 1, so moving here costs an additional 1 in health. Update dist[1][0] to 1, enqueue (1, 0) for further exploration.
  - (0, 1) is another valid neighbor. grid[0][1] is 1, resulting in a cost of 1 in health. Update dist[0][1] to 1, enqueue (0, 1) for exploration.
- Dequeue (1, 0). Check its neighbors:
  - (2, 0) is a valid neighbor. grid[2][0] is 0, thus no additional health cost. Update dist[2][0] to 1, enqueue (2, 0).
  - (1, 1) is a non-unsafe neighbor. grid[1][1] is 0, so dist[1][1] becomes 1. Enqueue (1, 1).
- Dequeue (0, 1). Explore its neighbors:
  - (0, 2) is a safe neighbor. grid[0][2] is 0. Update dist[0][2] to 1, enqueue (0, 2).
  - (1, 1) is already processed with the same cost; no update needed.
- Continue iterating similarly until all possible paths are explored.
Check Target:
- After processing, the dist for the target (2, 2) becomes dist[2][2] = 2. Since this is within our available health of 3, reaching (2, 2) with positive health is feasible.

Therefore, the result is true, indicating that the destination is reachable while maintaining positive health.

Solution Implementation

1from typing import List
2from collections import deque
3from math import inf
4
5class Solution:
6    def findSafeWalk(self, grid: List[List[int]], health: int) -> bool:
7        m, n = len(grid), len(grid[0])  # Dimensions of the grid
8        # Distance matrix initialized with infinity
9        dist = [[inf] * n for _ in range(m)]
10        dist[0][0] = grid[0][0]  # Starting point 
11        # Queue for BFS, starting from top-left corner
12        queue = deque([(0, 0)])  
13        # Directions for moving up, right, down, left
14        directions = (-1, 0, 1, 0, -1)  
15      
16        # Perform BFS to find the shortest path
17        while queue:
18            x, y = queue.popleft()  # Get current position
19            # Iterate over possible movements
20            for i in range(4):
21                nx, ny = x + directions[i], y + directions[i+1]
22                # Check if within bounds and if a shorter path is found
23                if (0 <= nx < m and 0 <= ny < n and 
24                    dist[nx][ny] > dist[x][y] + grid[nx][ny]):
25                    dist[nx][ny] = dist[x][y] + grid[nx][ny]  # Update distance
26                    queue.append((nx, ny))  # Enqueue new position
27      
28        # Check if the health is sufficient to reach the bottom-right corner
29        return dist[m-1][n-1] < health
30

1import java.util.*;
2
3class Solution {
4    public boolean findSafeWalk(List<List<Integer>> grid, int health) {
5        int m = grid.size();  // number of rows
6        int n = grid.get(0).size();  // number of columns
7        int[][] dist = new int[m][n];  // distance matrix to store minimum health cost to reach each cell
8
9        // Initialize distances with max value indicating unvisited or unreachable
10        for (int[] row : dist) {
11            Arrays.fill(row, Integer.MAX_VALUE);
12        }
13        // Start from the top left corner
14        dist[0][0] = grid.get(0).get(0);
15
16        // Queue for Breadth-First Search (BFS)
17        Deque<int[]> queue = new ArrayDeque<>();
18        queue.offer(new int[] {0, 0});
19
20        // Directions arrays for navigation (up, down, left, right)
21        final int[] directions = {-1, 0, 1, 0, -1};
22
23        // BFS loop
24        while (!queue.isEmpty()) {
25            int[] current = queue.poll();
26            int x = current[0];
27            int y = current[1];
28
29            // Explore neighbors
30            for (int i = 0; i < 4; i++) {
31                int newX = x + directions[i];
32                int newY = y + directions[i + 1];
33
34                // Check boundaries and if a shorter path is found
35                if (newX >= 0 && newX < m && newY >= 0 && newY < n
36                        && dist[newX][newY] > dist[x][y] + grid.get(newX).get(newY)) {
37                    dist[newX][newY] = dist[x][y] + grid.get(newX).get(newY);
38                    queue.offer(new int[] {newX, newY});
39                }
40            }
41        }
42
43        // Return true if a safe path exists under the given health constraint
44        return dist[m - 1][n - 1] < health;
45    }
46}
47

1class Solution {
2public:
3    // Determine if there is a safe walk to the bottom-right corner, staying within given health.
4    bool findSafeWalk(vector<vector<int>>& grid, int health) {
5        int rows = grid.size(); // Number of rows in the grid
6        int cols = grid[0].size(); // Number of columns in the grid
7
8        // Create a distance matrix initialized with maximum integer values to track minimum cost to each cell
9        vector<vector<int>> distance(rows, vector<int>(cols, INT_MAX));
10      
11        // Starting point has the cost of its own grid value
12        distance[0][0] = grid[0][0];
13      
14        // Queue for breadth-first search, starting at the top-left corner
15        queue<pair<int, int>> bfsQueue;
16        bfsQueue.emplace(0, 0);
17      
18        // Direction vectors for moving up, down, left, and right
19        int directions[5] = {-1, 0, 1, 0, -1};
20      
21        // BFS to explore all possible paths
22        while (!bfsQueue.empty()) {
23            auto [x, y] = bfsQueue.front();
24            bfsQueue.pop();
25          
26            // Explore the four possible directions
27            for (int i = 0; i < 4; ++i) {
28                int newX = x + directions[i];
29                int newY = y + directions[i + 1];
30              
31                // Check if the new position is within bounds and if a cheaper path is found
32                if (newX >= 0 && newX < rows && newY >= 0 && newY < cols &&
33                    distance[newX][newY] > distance[x][y] + grid[newX][newY]) {
34                  
35                    // Update the distance with the new minimum cost to reach (newX, newY)
36                    distance[newX][newY] = distance[x][y] + grid[newX][newY];
37                  
38                    // Add the new position to the queue for further exploration
39                    bfsQueue.emplace(newX, newY);
40                }
41            }
42        }
43      
44        // Return true if the cost to reach the bottom-right corner is less than the given health
45        return distance[rows - 1][cols - 1] < health;
46    }
47};
48

1// Determines if there is a safe walk from the top-left to the bottom-right of a grid
2// without exceeding the given health cost.
3function findSafeWalk(grid: number[][], health: number): boolean {
4    // Get the number of rows and columns in the grid
5    const rows = grid.length;
6    const cols = grid[0].length;
7
8    // Initialize a distance matrix filled with Infinity to track minimum path costs
9    const distance: number[][] = Array.from({ length: rows }, () => Array(cols).fill(Infinity));
10    // Starting point cost in the grid
11    distance[0][0] = grid[0][0];
12
13    // Queue to perform a Breadth-First Search (BFS), starting with the top-left cell
14    const queue: [number, number][] = [[0, 0]];
15
16    // Define the directions for moving up, right, down, and left
17    const directions = [-1, 0, 1, 0, -1];
18
19    // Process the queue until it's empty
20    while (queue.length > 0) {
21        // Dequeue the front element and explore neighboring cells
22        const [currentRow, currentCol] = queue.shift()!;
23
24        // Explore all four possible directions (up, right, down, and left)
25        for (let i = 0; i < 4; i++) {
26            const nextRow = currentRow + directions[i];
27            const nextCol = currentCol + directions[i + 1];
28
29            // Check if the new position is within bounds and offers a cheaper path
30            if (
31                nextRow >= 0 &&
32                nextRow < rows &&
33                nextCol >= 0 &&
34                nextCol < cols &&
35                distance[nextRow][nextCol] > distance[currentRow][currentCol] + grid[nextRow][nextCol]
36            ) {
37                // Update the minimum path cost to reach the new position
38                distance[nextRow][nextCol] = distance[currentRow][currentCol] + grid[nextRow][nextCol];
39                // Add the new position to the queue for further exploration
40                queue.push([nextRow, nextCol]);
41            }
42        }
43    }
44
45    // Return true if the cost to reach the bottom-right cell is less than the given health; otherwise, false
46    return distance[rows - 1][cols - 1] < health;
47}
48

Time and Space Complexity

The time complexity of the code is O(m * n) because each cell in the grid is visited at most once. The while loop iterates over all grid positions, which results in O(m * n) operations as we consider each cell for the possible shortest path calculation.

The space complexity is also O(m * n). This is due to the dist matrix, which is used to store the minimum health cost to reach each cell. It has the same dimensions as the grid (m by n), contributing to the overall space complexity.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Add another stack to store the minimums

Add a heap to store the minimums

Add a variable to track the minimum

Add a queue to store the minumums

I don’t know