We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find a Safe Walk Through a Grid

Difficulty: Medium

Problem 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.

Key Insights

  • The grid is represented as a binary matrix where 0 indicates a safe cell and 1 indicates an unsafe cell.
  • We can perform a breadth-first search (BFS) or depth-first search (DFS) to explore potential paths from the starting point to the destination.
  • A priority queue can be utilized to explore paths that minimize health loss first.
  • The health constraint must be managed dynamically as we traverse the grid.

Space and Time Complexity

Time Complexity: O(m * n) - each cell is processed at most once. Space Complexity: O(m * n) - for storing the state of visited cells and the queue.

Solution

To solve the problem, we will use a breadth-first search (BFS) approach with a priority queue (min-heap) to explore the grid. Starting from the top-left corner, we will explore all four possible directions (up, down, left, right) while keeping track of the remaining health. If we reach the bottom-right corner with health greater than or equal to 1, we will return true. If we exhaust all possible paths without meeting the condition, we return false.

The BFS will involve:

  1. Initializing a priority queue to store the current position and remaining health.
  2. Marking cells as visited to avoid cycles.
  3. Iterating through possible moves and updating health based on whether the next cell is safe or unsafe.
  4. Stopping when we reach the destination or when there are no more cells to process.

Code Solutions

from collections import deque

def canReach(grid, health):
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    queue = deque([(0, 0, health)])  # (row, col, remaining health)
    visited = set((0, 0))

    while queue:
        r, c, h = queue.popleft()
        
        # If we reached the bottom-right corner with health >= 1
        if r == rows - 1 and c == cols - 1 and h >= 1:
            return True
        
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            
            if 0 <= nr < rows and 0 <= nc < cols:
                new_health = h - grid[nr][nc]
                if new_health > 0 and (nr, nc) not in visited:
                    visited.add((nr, nc))
                    queue.append((nr, nc, new_health))
    
    return False
← Back to All Questions