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 the Safest Path in a Grid

Difficulty: Medium

Problem Description

You are given a 0-indexed 2D matrix grid of size n x n, where (r, c) represents a cell containing a thief if grid[r][c] = 1 and an empty cell if grid[r][c] = 0. You are initially positioned at cell (0, 0). In one move, you can move to any adjacent cell in the grid, including cells containing thieves. The safeness factor of a path on the grid is defined as the minimum Manhattan distance from any cell in the path to any thief in the grid. Return the maximum safeness factor of all paths leading to cell (n - 1, n - 1).

Key Insights

  • The problem requires finding paths in a grid while maximizing the minimum distance to any thieves.
  • The Manhattan distance is crucial for determining the safeness factor.
  • A breadth-first search (BFS) can be used to explore the grid and determine distances from thieves.
  • Binary search can help to optimize finding the maximum safeness factor.

Space and Time Complexity

Time Complexity: O(n^2 log(n)), where n is the grid size due to BFS and binary search. Space Complexity: O(n^2), primarily for storing distances and the grid.

Solution

To solve the problem, we can use a combination of BFS and binary search. First, we identify the positions of all thieves in the grid. Then, we perform a BFS from each thief to calculate the minimum Manhattan distance from any cell in the grid to the nearest thief. This distance is stored in a 2D array. With this information, we can then use binary search to find the maximum safeness factor that allows a valid path from (0, 0) to (n - 1, n - 1). During the binary search, we will check for the existence of a valid path using BFS or DFS that maintains the safeness factor greater than or equal to the mid-point of our current search range.

Code Solutions

from collections import deque

def maxSafenessFactor(grid):
    n = len(grid)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    
    # BFS to calculate the distance from each thief
    def bfs():
        distance = [[float('inf')] * n for _ in range(n)]
        queue = deque()
        
        for r in range(n):
            for c in range(n):
                if grid[r][c] == 1:
                    queue.append((r, c))
                    distance[r][c] = 0
        
        while queue:
            r, c = queue.popleft()
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    if distance[nr][nc] > distance[r][c] + 1:
                        distance[nr][nc] = distance[r][c] + 1
                        queue.append((nr, nc))
        
        return distance
    
    # Check if there is a valid path with at least safeness factor
    def canReach(safeness, distance):
        if distance[0][0] < safeness or distance[n-1][n-1] < safeness:
            return False
        
        queue = deque([(0, 0)])
        visited = set((0, 0))
        
        while queue:
            r, c = queue.popleft()
            if (r, c) == (n-1, n-1):
                return True
            
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n and (nr, nc) not in visited:
                    if distance[nr][nc] >= safeness:
                        visited.add((nr, nc))
                        queue.append((nr, nc))
        
        return False
    
    distance = bfs()
    
    # Binary search for the maximum safeness factor
    left, right = 0, n * 2  # maximum distance possible
    while left < right:
        mid = (left + right + 1) // 2
        if canReach(mid, distance):
            left = mid
        else:
            right = mid - 1
    
    return left
← Back to All Questions