Find the Safest Path in a Grid

1class SafestPathFinder {
2    constructor() {
3        this.directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
4    }
5
6    maxSafenessFactor(grid) {
7        const n = grid.length;
8        const distance = Array.from({ length: n }, () => Array(n).fill(Infinity));
9        const queue = [];
10
11        for (let r = 0; r < n; r++) {
12            for (let c = 0; c < n; c++) {
13                if (grid[r][c] === 1) {
14                    queue.push([r, c]);
15                    distance[r][c] = 0;
16                }
17            }
18        }
19
20        let idx = 0;
21        while (idx < queue.length) {
22            const [r, c] = queue[idx++];
23            for (const [dr, dc] of this.directions) {
24                const nr = r + dr, nc = c + dc;
25                if (nr >= 0 && nr < n && nc >= 0 && nc < n && distance[nr][nc] === Infinity) {
26                    distance[nr][nc] = distance[r][c] + 1;
27                    queue.push([nr, nc]);
28                }
29            }
30        }
31
32        const heap = new MaxPriorityQueue({ priority: x => x[2] });
33        heap.enqueue([0, 0, distance[0][0]]);
34
35        const visited = Array.from({ length: n }, () => Array(n).fill(false));
36
37        while (!heap.isEmpty()) {
38            const { element: [r, c, safeness] } = heap.dequeue();
39            if (r === n - 1 && c === n - 1) return safeness;
40            if (visited[r][c]) continue;
41            visited[r][c] = true;
42
43            for (const [dr, dc] of this.directions) {
44                const nr = r + dr, nc = c + dc;
45                if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
46                    const newSafeness = Math.min(safeness, distance[nr][nc]);
47                    heap.enqueue([nr, nc, newSafeness]);
48                }
49            }
50        }
51        return 0;
52    }
53}
54
55const spf = new SafestPathFinder();
56const grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]];
57console.log(spf.maxSafenessFactor(grid)); // Output: 2
58

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