Find the Safest Path in a Grid

1import heapq
2
3class SafestPathFinder:
4    def maxSafenessFactor(self, grid):
5        n = len(grid)
6        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
7        distance = [[float('inf')] * n for _ in range(n)]
8        q = []
9
10        # BFS from all thieves
11        for r in range(n):
12            for c in range(n):
13                if grid[r][c] == 1:
14                    q.append((r, c))
15                    distance[r][c] = 0
16
17        for r, c in q:
18            for dr, dc in directions:
19                nr, nc = r + dr, c + dc
20                if 0 <= nr < n and 0 <= nc < n and distance[nr][nc] == float('inf'):
21                    distance[nr][nc] = distance[r][c] + 1
22                    q.append((nr, nc))
23
24        # Max-safeness factor using a max-heap
25        heap = [(-distance[0][0], 0, 0)]  # store as negative for max-heap behavior
26        maxSafeness = [[-1] * n for _ in range(n)]
27        maxSafeness[0][0] = distance[0][0]
28
29        while heap:
30            safeness, r, c = heapq.heappop(heap)
31            safeness = -safeness
32
33            for dr, dc in directions:
34                nr, nc = r + dr, c + dc
35                if 0 <= nr < n and 0 <= nc < n:
36                    newSafeness = min(safeness, distance[nr][nc])
37                    if newSafeness > maxSafeness[nr][nc]:
38                        maxSafeness[nr][nc] = newSafeness
39                        heapq.heappush(heap, (-newSafeness, nr, nc))
40
41        return maxSafeness[n-1][n-1]
42
43# Example usage
44spf = SafestPathFinder()
45grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]]
46print(spf.maxSafenessFactor(grid))  # Output: 2
47

1import java.util.*;
2
3public class SafestPathFinder {
4    private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
5
6    public int bidirectionalSafenessFactor(int[][] grid) {
7        int n = grid.length;
8        int[][] distFromStart = new int[n][n];
9        int[][] distFromEnd = new int[n][n];
10        for (int[] row : distFromStart) Arrays.fill(row, Integer.MAX_VALUE);
11        for (int[] row : distFromEnd) Arrays.fill(row, Integer.MAX_VALUE);
12
13        Queue<int[]> startQueue = new LinkedList<>();
14        startQueue.offer(new int[]{0, 0});
15        distFromStart[0][0] = 0;
16
17        Queue<int[]> endQueue = new LinkedList<>();
18        endQueue.offer(new int[]{n - 1, n - 1});
19        distFromEnd[n - 1][n - 1] = 0;
20
21        while (!startQueue.isEmpty() || !endQueue.isEmpty()) {
22            if (!startQueue.isEmpty()) {
23                int[] pos = startQueue.poll();
24                int r = pos[0], c = pos[1];
25                for (int[] dir : directions) {
26                    int nr = r + dir[0], nc = c + dir[1];
27                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] == Integer.MAX_VALUE) {
28                        distFromStart[nr][nc] = distFromStart[r][c] + 1;
29                        startQueue.offer(new int[]{nr, nc});
30                    }
31                }
32            }
33
34            if (!endQueue.isEmpty()) {
35                int[] pos = endQueue.poll();
36                int r = pos[0], c = pos[1];
37                for (int[] dir : directions) {
38                    int nr = r + dir[0], nc = c + dir[1];
39                    if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromEnd[nr][nc] == Integer.MAX_VALUE) {
40                        distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
41                        endQueue.offer(new int[]{nr, nc});
42                    }
43                }
44            }
45
46            // Checking overlap
47            for (int i = 0; i < n; ++i) {
48                for (int j = 0; j < n; ++j) {
49                    if (distFromStart[i][j] != Integer.MAX_VALUE && distFromEnd[i][j] != Integer.MAX_VALUE) {
50                        return distFromStart[i][j] + distFromEnd[i][j];
51                    }
52                }
53            }
54        }
55
56        return -1;
57    }
58
59    public static void main(String[] args) {
60        SafestPathFinder spf = new SafestPathFinder();
61        int[][] grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
62        System.out.println(spf.bidirectionalSafenessFactor(grid)); // Output: Safeness factor
63    }
64}
65