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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Find a Safe Walk Through a Grid

Number: 3558

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg

Problem Description

Given an m x n binary matrix grid and an integer health, you start at the top-left cell (0, 0) and want to reach the bottom-right cell (m - 1, n - 1). You are allowed to move up, down, left or right as long as, after each move (and applying any health reduction if the cell is unsafe), your health remains positive. A cell with grid[i][j] = 1 is considered unsafe and causes your health to decrease by 1 when you step into it. Return true if you can reach the target cell (with health >= 1) and false otherwise.

Key Insights

  • Use a traversal algorithm (BFS or Dijkstra-style search) to explore paths while maintaining the current health.
  • When moving to a new cell, subtract 1 from the current health if the cell is unsafe (grid value 1).
  • The starting cell does not deduct health upon entry.
  • To avoid reprocessing states, record the maximum health you had when arriving at a given cell and prune paths that do not yield an improvement.
  • Since grid dimensions are small (up to 50x50) and health is bounded by m+n, a state-space search with pruning is efficient.

Space and Time Complexity

Time Complexity: O(m * n * H) where H is the maximum health value, since each cell may be visited with different remaining health values. Space Complexity: O(m * n * H) for the memoization structure that tracks the maximum health obtained at each cell.

Solution

We solve the problem using a Breadth-First Search (BFS). Each state is represented by (row, col, currentHealth), where currentHealth is the remaining health at that position. Starting at (0, 0) with the given health (without any deduction on the start cell), we attempt to move in the four cardinal directions. For every move, if the target cell is unsafe, we decrement the health by 1. We only continue exploring a new state if the resulting health is positive. To ensure efficiency and avoid revisiting states with inferior health, we maintain a 2D array that records the highest health seen so far at each cell. If the current state’s health is not better than a previously recorded one at the same cell, we skip it. The search terminates early when we reach the destination with a positive health.

Code Solutions

# Python solution using BFS with state pruning
from collections import deque

def safeWalk(grid, health):
    m, n = len(grid), len(grid[0])
    # Directions: up, down, left, right
    directions = [(-1,0), (1,0), (0,-1), (0,1)]
    
    # visited[i][j] holds the maximum health reached at cell (i, j)
    visited = [[-1] * n for _ in range(m)]
    # Start from (0,0) with initial health (do not subtract cost from starting cell)
    queue = deque([(0, 0, health)])
    visited[0][0] = health
    
    while queue:
        i, j, currHealth = queue.popleft()
        # When we reach the destination with health > 0, return True
        if i == m - 1 and j == n - 1:
            return True
        
        for di, dj in directions:
            new_i, new_j = i + di, j + dj
            # Check if new coordinates are within grid bounds
            if 0 <= new_i < m and 0 <= new_j < n:
                # If cell is unsafe, subtract health
                nextHealth = currHealth - (1 if grid[new_i][new_j] == 1 else 0)
                # Only proceed if nextHealth remains positive
                if nextHealth > 0 and nextHealth > visited[new_i][new_j]:
                    visited[new_i][new_j] = nextHealth
                    queue.append((new_i, new_j, nextHealth))
                    
    return False

# Example usage:
grid1 = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0]]
print(safeWalk(grid1, 1))  # Expected True
← Back to All Questions