1class Solution {
2    public int maximumSafenessFactor(List<List<Integer>> grid) {
3        int n = grid.size();
4      
5        // Check for obstacles at start or end positions.
6        if (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) {
7            return 0; // No path if start or end is blocked.
8        }
9      
10        Deque<int[]> queue = new ArrayDeque<>();
11        int[][] distances = new int[n][n];
12        final int INF = 1 << 30;
13      
14        // Initialize distances to "infinity"
15        for (int[] distanceRow : distances) {
16            Arrays.fill(distanceRow, INF);
17        }
18      
19        // Initial distance for all obstacles set to 0 and added to queue.
20        for (int i = 0; i < n; ++i) {
21            for (int j = 0; j < n; ++j) {
22                if (grid.get(i).get(j) == 1) {
23                    distances[i][j] = 0;
24                    queue.offer(new int[] {i, j});
25                }
26            }
27        }
28      
29        // Directions for up, right, down, left traversal.
30        int[] directionDeltas = {-1, 0, 1, 0, -1};
31      
32        // Perform a multi-source BFS to find shortest distance to obstacles for each cell.
33        while (!queue.isEmpty()) {
34            int[] position = queue.poll();
35            int i = position[0], j = position[1];
36            for (int k = 0; k < 4; ++k) {
37                int x = i + directionDeltas[k], y = j + directionDeltas[k + 1];
38                if (x >= 0 && x < n && y >= 0 && y < n && distances[x][y] == INF) {
39                    distances[x][y] = distances[i][j] + 1;
40                    queue.offer(new int[] {x, y});
41                }
42            }
43        }
44      
45        // Store each cell as [distance, row, column].
46        List<int[]> sortedCellsByDistance = new ArrayList<>();
47        for (int i = 0; i < n; ++i) {
48            for (int j = 0; j < n; ++j) {
49                sortedCellsByDistance.add(new int[] {distances[i][j], i, j});
50            }
51        }
52      
53        // Sort cells by distance in descending order.
54        sortedCellsByDistance.sort((a, b) -> Integer.compare(b[0], a[0]));
55      
56        UnionFind unionFind = new UnionFind(n * n);
57      
58        // Try to connect cells starting with the safest (largest distance).
59        for (int[] cell : sortedCellsByDistance) {
60            int distance = cell[0], i = cell[1], j = cell[2];
61            for (int k = 0; k < 4; ++k) {
62                int x = i + directionDeltas[k], y = j + directionDeltas[k + 1];
63                if (x >= 0 && x < n && y >= 0 && y < n && distances[x][y] >= distance) {
64                    unionFind.union(i * n + j, x * n + y);
65                }
66            }
67            // Check if start is connected to end.
68            if (unionFind.find(0) == unionFind.find(n * n - 1)) {
69                return distance;
70            }
71        }
72        return 0; // If no path is found.
73    }
74}
75
76class UnionFind {
77    private int[] parents;
78    private int count;
79
80    public UnionFind(int totalNodes) {
81        parents = new int[totalNodes];
82        for (int i = 0; i < totalNodes; ++i) {
83            parents[i] = i; // Each node is its own parent at the beginning.
84        }
85        this.count = totalNodes;
86    }
87
88    public boolean union(int a, int b) {
89        int parentA = find(a);
90        int parentB = find(b);
91        if (parentA == parentB) {
92            return false;
93        }
94        parents[parentA] = parentB;
95        --count;
96        return true;
97    }
98
99    public int find(int x) {
100        if (parents[x] != x) {
101            parents[x] = find(parents[x]);
102        }
103        return parents[x];
104    }
105}
106

1#include <vector>
2#include <numeric>
3#include <queue>
4#include <tuple>
5#include <cstring>
6#include <algorithm>
7
8using namespace std;
9
10class UnionFind {
11public:
12    vector<int> parent;
13    int count;
14
15    // Constructor initializes UnionFind with `n` elements
16    UnionFind(int n)
17        : count(n), parent(n) {
18        // Fill the parent vector with indices of itself (self parentage)
19        iota(parent.begin(), parent.end(), 0);
20    }
21
22    // Unite two groups; if they are already united, return false
23    bool unite(int a, int b) {
24        int rootA = find(a), rootB = find(b);
25        if (rootA == rootB) return false;
26        // Assign the parent of A's root to be B's root
27        parent[rootA] = rootB;
28        --count; // Decrease the number of disjoint sets
29        return true;
30    }
31
32    // Find the root of the group that element `x` is in
33    int find(int x) {
34        // Path compression: point this node directly to the root
35        if (parent[x] != x) parent[x] = find(parent[x]);
36        return parent[x];
37    }
38};
39
40class Solution {
41public:
42    // Calculates the maximum safeness factor of a given grid
43    int maximumSafenessFactor(vector<vector<int>>& grid) {
44        int gridSize = grid.size();
45        // If the start or end points are blocked, return 0
46        if (grid[0][0] || grid[gridSize - 1][gridSize - 1]) {
47            return 0;
48        }
49
50        queue<pair<int, int>> q; // Queue for BFS
51        // Initialize distance array with large values
52        int dist[gridSize][gridSize];
53        memset(dist, 0x3f, sizeof(dist));
54
55        // Calculate distances from each hazard in the grid
56        for (int i = 0; i < gridSize; ++i) {
57            for (int j = 0; j < gridSize; ++j) {
58                if (grid[i][j]) {
59                    dist[i][j] = 0; // Hazards have zero distance
60                    q.emplace(i, j); // Add hazards to the queue
61                }
62            }
63        }
64
65        // Directions for neighbors (up, right, down, left)
66        int dirs[5] = {-1, 0, 1, 0, -1};
67
68        // Perform BFS to calculate the distance of each cell from the closest hazard
69        while (!q.empty()) {
70            auto [i, j] = q.front();
71            q.pop();
72            for (int k = 0; k < 4; ++k) {
73                int x = i + dirs[k], y = j + dirs[k + 1];
74                if (x >= 0 && x < gridSize && y >= 0 && y < gridSize && 
75                    dist[x][y] == 0x3f3f3f3f) {
76                    dist[x][y] = dist[i][j] + 1; // Update distance
77                    q.emplace(x, y); // Enqueue the current cell
78                }
79            }
80        }
81
82        // Sort the cells by distance in descending order
83        vector<tuple<int, int, int>> distances;
84        for (int i = 0; i < gridSize; ++i) {
85            for (int j = 0; j < gridSize; ++j) {
86                distances.emplace_back(dist[i][j], i, j);
87            }
88        }
89        sort(distances.begin(), distances.end(), greater<>());
90
91        // UnionFind to keep track of connectivity
92        UnionFind uf(gridSize * gridSize);
93
94        // Try to unite cells, starting from the highest distance from hazards
95        for (auto [distance, i, j] : distances) {
96            for (int k = 0; k < 4; ++k) {
97                int x = i + dirs[k], y = j + dirs[k + 1];
98                if (x >= 0 && x < gridSize && y >= 0 && y < gridSize && dist[x][y] >= distance) {
99                    uf.unite(i * gridSize + j, x * gridSize + y);
100                }
101            }
102            // If the start and end points are connected, return the current distance
103            if (uf.find(0) == uf.find(gridSize * gridSize - 1)) {
104                return distance;
105            }
106        }
107
108        // If no path is found, return 0
109        return 0;
110    }
111};
112

1// Size of the grid
2let size: number = 0;
3// Array to store the parent of each element
4let parent: number[] = [];
5
6// Initializes the array for union-find operations with each element as its own parent
7function initializeUnionFind(n: number): void {
8    size = n;
9    parent = new Array(n * n).fill(0).map((_, index) => index);
10}
11
12// Finds the parent of a given element `x` and applies path compression
13function find(x: number): number {
14    if (parent[x] !== x) {
15        parent[x] = find(parent[x]);
16    }
17    return parent[x];
18}
19
20// Unites two elements `a` and `b`. Returns true if they're connected, false otherwise
21function union(a: number, b: number): boolean {
22    const rootA = find(a);
23    const rootB = find(b);
24    if (rootA !== rootB) {
25        parent[rootA] = rootB;
26        size--;
27        return true;
28    }
29    return false;
30}
31
32// Calculates the maximum safeness factor for a given grid
33function maximumSafenessFactor(grid: number[][]): number {
34    const n = grid.length;
35    // If the starting or ending cell is blocked, return 0
36    if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) {
37        return 0;
38    }
39  
40    // Multi-directions for traversing adjacent cells
41    const directions = [-1, 0, 1, 0, -1]; 
42    // Queue for BFS
43    const queue: number[][] = [];
44    // Distance array with initial distances set to infinity
45    const distance: number[][] = Array(n)
46        .fill(0)
47        .map(() => Array(n).fill(Number.POSITIVE_INFINITY));
48    for (let i = 0; i < n; ++i) {
49        for (let j = 0; j < n; ++j) {
50            if (grid[i][j] === 1) {
51                distance[i][j] = 0;
52                queue.push([i, j]);
53            }
54        }
55    }
56  
57    // BFS to determine the shortest distance to the nearest obstacle for each cell
58    while (queue.length > 0) {
59        const [currentRow, currentColumn] = queue.shift()!;
60        for (let k = 0; k < 4; ++k) {
61            const nextRow = currentRow + directions[k];
62            const nextColumn = currentColumn + directions[k + 1];
63            if (nextRow >= 0 && nextRow < n && nextColumn >= 0 && nextColumn < n && distance[nextRow][nextColumn] === Number.POSITIVE_INFINITY) {
64                distance[nextRow][nextColumn] = distance[currentRow][currentColumn] + 1;
65                queue.push([nextRow, nextColumn]);
66            }
67        }
68    }
69  
70    // Flattened and sorted list of the grid cells together with their distances
71    const sortedCells: [number, number, number][] = [];
72    for (let i = 0; i < n; ++i) {
73        for (let j = 0; j < n; ++j) {
74            sortedCells.push([distance[i][j], i, j]);
75        }
76    }
77    sortedCells.sort((cell1, cell2) => cell2[0] - cell1[0]);
78  
79    // Initialize union-find structure
80    initializeUnionFind(n);
81  
82    // Connect cells in order of highest distance to lowest
83    for (const [dist, row, column] of sortedCells) {
84        for (let k = 0; k < 4; ++k) {
85            const nextRow = row + directions[k];
86            const nextColumn = column + directions[k + 1];
87            if (nextRow >= 0 && nextRow < n && nextColumn >= 0 && nextColumn < n && distance[nextRow][nextColumn] >= dist) {
88                union(row * n + column, nextRow * n + nextColumn);
89            }
90        }
91        // If the start and end cells are connected, return the current distance
92        if (find(0) === find(n * n - 1)) {
93            return dist;
94        }
95    }
96    // If no safe path is found, return 0
97    return 0;
98}
99