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

1#include <iostream>
2#include <vector>
3#include <queue>
4#include <climits>
5
6using namespace std;
7
8const int directions[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
9
10int bidirectionalSafenessFactor(vector<vector<int>>& grid) {
11    int n = grid.size();
12    vector<vector<int>> distFromStart(n, vector<int>(n, INT_MAX));
13    vector<vector<int>> distFromEnd(n, vector<int>(n, INT_MAX));
14
15    queue<pair<int, int>> startQueue;
16    startQueue.push({0, 0});
17    distFromStart[0][0] = 0;
18
19    queue<pair<int, int>> endQueue;
20    endQueue.push({n - 1, n - 1});
21    distFromEnd[n - 1][n - 1] = 0;
22
23    while (!startQueue.empty() || !endQueue.empty()) {
24        if (!startQueue.empty()) {
25            auto [r, c] = startQueue.front(); startQueue.pop();
26            for (auto& dir : directions) {
27                int nr = r + dir[0], nc = c + dir[1];
28                if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] == INT_MAX) {
29                    distFromStart[nr][nc] = distFromStart[r][c] + 1;
30                    startQueue.push({nr, nc});
31                }
32            }
33        }
34
35        if (!endQueue.empty()) {
36            auto [r, c] = endQueue.front(); endQueue.pop();
37            for (auto& 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] == INT_MAX) {
40                    distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
41                    endQueue.push({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] != INT_MAX && distFromEnd[i][j] != INT_MAX) {
50                    return distFromStart[i][j] + distFromEnd[i][j];
51                }
52            }
53        }
54    }
55
56    return -1;
57}
58
59int main() {
60    vector<vector<int>> grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
61    cout << bidirectionalSafenessFactor(grid) << endl; // Output: Safeness factor
62    return 0;
63}
64