Find the Safest Path in a Grid

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
• 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).

An adjacent cell of cell (r, c), is one of the cells (r, c + 1), (r, c - 1), (r + 1, c) and (r - 1, c) if it exists.

The Manhattan distance between two cells (a, b) and (x, y) is equal to |a - x| + |b - y|, where |val| denotes the absolute value of val.

For example:

grid = [[1,0,0],[0,0,0],[0,0,1]]

Output: 0

Explanation: All paths from (0, 0) to (n - 1, n - 1) go through the thieves in cells (0, 0) and (n - 1, n - 1).

grid = [[0,0,1],[0,0,0],[0,0,0]]

Output: 2

Explanation: The path from (0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2) has a safeness factor of 2 since the closest cell of the path to the thief at cell (0, 2) is cell (0, 0). The distance between them is | 0 - 0 | + | 0 - 2 | = 2.

What is the optimal algorithm to solve this problem?

Brute Force Solution

The brute force approach would involve checking every possible path from (0, 0) to (n-1, n-1) and calculating the safeness factor for each path. We can use Depth-First Search (DFS) to explore all possible paths. For each path, we calculate the minimum Manhattan distance from each cell in the path to every thief in the grid. The maximum of these minimum distances, across all paths, is the answer.

def manhattan_distance(r1, c1, r2, c2):
    return abs(r1 - r2) + abs(c1 - c2)


def calculate_safeness(path, thieves):
    safeness = float('inf')
    for r, c in path:
        min_dist = float('inf')
        for tr, tc in thieves:
            min_dist = min(min_dist, manhattan_distance(r, c, tr, tc))
        safeness = min(safeness, min_dist)
    return safeness


def find_paths(grid):
    n = len(grid)
    thieves = []
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                thieves.append((r, c))
    
    paths = []
    
    def dfs(r, c, current_path):
        if r < 0 or r >= n or c < 0 or c >= n or (r, c) in current_path:
            return
        
        current_path.append((r, c))
        
        if r == n - 1 and c == n - 1:
            paths.append(current_path[:])  # Append a copy to avoid modification
            current_path.pop()
            return
        
        dfs(r + 1, c, current_path)
        dfs(r - 1, c, current_path)
        dfs(r, c + 1, current_path)
        dfs(r, c - 1, current_path)
        
        current_path.pop()
    
    dfs(0, 0, [])
    return paths, thieves


def maximum_safeness_factor_brute_force(grid):
    paths, thieves = find_paths(grid)
    if not paths:
        return 0 # No path exists
        
    max_safeness = 0
    for path in paths:
        max_safeness = max(max_safeness, calculate_safeness(path, thieves))
    return max_safeness

# Example usage
grid1 = [[1,0,0],[0,0,0],[0,0,1]]
print(f"Brute Force Safeness factor for grid1: {maximum_safeness_factor_brute_force(grid1)}")

grid2 = [[0,0,1],[0,0,0],[0,0,0]]
print(f"Brute Force Safeness factor for grid2: {maximum_safeness_factor_brute_force(grid2)}")

grid3 = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
print(f"Brute Force Safeness factor for grid3: {maximum_safeness_factor_brute_force(grid3)}")

Optimal Solution: Binary Search + BFS

An optimized approach uses binary search to find the maximum possible safeness factor. For each potential safeness factor k, we use Breadth-First Search (BFS) to check if there exists a path from (0, 0) to (n-1, n-1) where all cells in the path have a Manhattan distance of at least k to the nearest thief.

Here's the breakdown:

1. Calculate distances to nearest thief: For each cell in the grid, compute the Manhattan distance to the nearest thief. This can be done efficiently using BFS starting from all thief cells simultaneously.
2. Binary Search: Perform a binary search on the possible range of safeness factors (0 to maximum possible distance). For a given mid-value k (potential safeness factor):
   • BFS with safeness constraint: Run BFS from (0, 0) to (n-1, n-1), but only allow moves to adjacent cells that have a distance of at least k to the nearest thief. If a path exists, it means k is a feasible safeness factor, so try a higher value. Otherwise, try a lower value.
3. Return the maximum feasible safeness factor.

from collections import deque

def maximum_safeness_factor(grid):
    n = len(grid)

    # Calculate distances to the nearest thief for each cell
    distances = calculate_distances(grid)

    # Binary search for the maximum safeness factor
    left, right = 0, 2 * n - 2  # Max possible Manhattan distance
    ans = 0

    while left <= right:
        mid = (left + right) // 2
        if can_reach_destination(grid, distances, mid):
            ans = mid
            left = mid + 1  # Try to increase safeness factor
        else:
            right = mid - 1  # Decrease safeness factor

    return ans


def calculate_distances(grid):
    n = len(grid)
    distances = [[float('inf')] * n for _ in range(n)]
    queue = deque()

    # Add all thieves to the queue and set their distance to 0
    for r in range(n):
        for c in range(n):
            if grid[r][c] == 1:
                distances[r][c] = 0
                queue.append((r, c))

    # BFS to calculate distances
    while queue:
        r, c = queue.popleft()
        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and distances[nr][nc] == float('inf'):
                distances[nr][nc] = distances[r][c] + 1
                queue.append((nr, nc))

    return distances


def can_reach_destination(grid, distances, safeness):
    n = len(grid)
    if distances[0][0] < safeness or distances[n-1][n-1] < safeness: #optimization: cannot reach if either start or end are too close
      return False
    visited = [[False] * n for _ in range(n)]
    queue = deque([(0, 0)])
    visited[0][0] = True

    while queue:
        r, c = queue.popleft()

        if r == n - 1 and c == n - 1:
            return True

        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and not visited[nr][nc] and distances[nr][nc] >= safeness:
                queue.append((nr, nc))
                visited[nr][nc] = True

    return False


# Example usage
grid1 = [[1,0,0],[0,0,0],[0,0,1]]
print(f"Optimal Safeness factor for grid1: {maximum_safeness_factor(grid1)}")

grid2 = [[0,0,1],[0,0,0],[0,0,0]]
print(f"Optimal Safeness factor for grid2: {maximum_safeness_factor(grid2)}")

grid3 = [[0,0,0,1],[0,0,0,0],[0,0,0,0],[1,0,0,0]]
print(f"Optimal Safeness factor for grid3: {maximum_safeness_factor(grid3)}")

Time Complexity Analysis

• Brute Force (DFS): O(4^(n^2)). In the worst case, the DFS explores all possible paths, which can grow exponentially with the grid size. For each path, calculating safeness is O(n^2 * number of thieves) in the worst case, since the path can have at most n^2 steps and there are at most n^2 thieves. The overall complexity is dominated by the path exploration, making it O(4^(n^2)). The '4' comes from the 4 directions to move at each position.
• Optimal (Binary Search + BFS): O(n^2 log n).
  • Calculating distances to the nearest thief using BFS: O(n^2), because each cell is visited at most once.
  • Binary search: O(log n), where 'n' is the maximum possible safeness factor, which is at most 2 * (n-1).
  • For each mid-value in the binary search, we perform a BFS: O(n^2).
  • Therefore, the overall time complexity is O(n^2 + log n * n^2) = O(n^2 log n).

Space Complexity Analysis

• Brute Force (DFS): O(n^2). The maximum depth of the recursion is n^2. The path variable can grow to n^2 size, and is copied for each path, so the storage of the paths also grows to be large.
• Optimal (Binary Search + BFS): O(n^2).
  • The distances array requires O(n^2) space.
  • The visited array in can_reach_destination requires O(n^2) space.
  • The queue in both BFS traversals can hold at most all the cells in the grid, requiring O(n^2) space.

Edge Cases and Handling

1. No path exists: The code should handle the case where there is no valid path from the starting cell to the destination cell. In the brute-force approach, if paths is empty, the function returns 0. In the optimal approach, if can_reach_destination always returns false, the binary search will converge to 0.
2. No thieves in the grid: The problem states there is at least one thief, so this edge case doesn't need to be explicitly handled. However, if there were no thieves, the distances would remain infinity, and all paths would be safe (safeness factor of infinity). In a practical implementation, an additional check at the beginning could handle this by returning a large value (e.g., 2 * n - 2) to indicate infinite safeness.
3. Grid size of 1x1: The code should correctly handle a 1x1 grid. Both the brute force and optimized approaches will work.
4. Thieves at the start or end: The Manhattan distance calculation correctly handles cases where the start or end cell contains a thief (distance is 0).
5. Large grid: For large grids, the brute force will definitely time out. The optimized solution uses binary search and BFS which avoids calculating all paths, so should work fine even for grids of size 400x400.