This approach involves using Breadth-First Search (BFS) to precompute the minimum Manhattan distance from each cell to any thief in the grid, and then using this information to find the maximum safeness factor for reaching the bottom-right corner.
Time Complexity: O(n2 log n), where n is the grid size, due to the Dijkstra-like process.
Space Complexity: O(n2) for storing distances and safeness factors.
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 maxSafenessFactor(vector<vector<int>>& grid) {
11 int n = grid.size();
12 vector<vector<int>> distance(n, vector<int>(n, INT_MAX));
13 queue<pair<int, int>> q;
14
15 // BFS to calculate initial distances to the nearest thief
16 for (int r = 0; r < n; ++r) {
17 for (int c = 0; c < n; ++c) {
18 if (grid[r][c] == 1) {
19 q.push({r, c});
20 distance[r][c] = 0;
21 }
22 }
23 }
24
25 while (!q.empty()) {
26 auto [r, c] = q.front(); q.pop();
27 for (auto& dir : directions) {
28 int nr = r + dir[0], nc = c + dir[1];
29 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distance[nr][nc] == INT_MAX) {
30 distance[nr][nc] = distance[r][c] + 1;
31 q.push({nr, nc});
32 }
33 }
34 }
35
36 // Use max-heap for Dijkstra's algorithm to find the path with the max safeness factor
37 vector<vector<int>> maxSafeness(n, vector<int>(n, -1));
38 priority_queue<pair<int, pair<int, int>>> pq;
39 pq.push({distance[0][0], {0, 0}});
40 maxSafeness[0][0] = distance[0][0];
41
42 while (!pq.empty()) {
43 auto [safeness, pos] = pq.top(); pq.pop();
44 auto [r, c] = pos;
45
46 for (auto& dir : directions) {
47 int nr = r + dir[0], nc = c + dir[1];
48 if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
49 int newSafeness = min(safeness, distance[nr][nc]);
50 if (newSafeness > maxSafeness[nr][nc]) {
51 maxSafeness[nr][nc] = newSafeness;
52 pq.push({newSafeness, {nr, nc}});
53 }
54 }
55 }
56 }
57
58 return maxSafeness[n-1][n-1];
59}
60
61int main() {
62 vector<vector<int>> grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
63 cout << maxSafenessFactor(grid) << endl; // Output: 2
64 return 0;
65}
66This C++ solution employs a BFS to determine the minimum Manhattan distance from every cell to any thief. A priority queue (max-heap) then executes Dijkstra's algorithm to ascertain the path with the maximum safeness factor to the target cell.
This approach considers processing from both the starting and ending points in a bidirectional BFS style, potentially meeting in the middle for optimized distance calculations and safeness factor determination.
Time Complexity: O(n2) due to simultaneous BFS processing.
Space Complexity: O(n2) as distances from both ends are computed.
1class SafestPathFinder {
2 constructor() {
3 this.directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
4 }
5
6 bidirectionalSafenessFactor(grid) {
7 const n = grid.length;
8 const distFromStart = Array.from({ length: n }, () => Array(n).fill(Infinity));
9 const distFromEnd = Array.from({ length: n }, () => Array(n).fill(Infinity));
10
11 const startQueue = [[0, 0]];
12 distFromStart[0][0] = 0;
13
14 const endQueue = [[n - 1, n - 1]];
15 distFromEnd[n - 1][n - 1] = 0;
16
17 while (startQueue.length || endQueue.length) {
18 if (startQueue.length) {
19 const [r, c] = startQueue.shift();
20 for (const [dr, dc] of this.directions) {
21 const nr = r + dr, nc = c + dc;
22 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] === Infinity) {
23 distFromStart[nr][nc] = distFromStart[r][c] + 1;
24 startQueue.push([nr, nc]);
25 }
26 }
27 }
28
29 if (endQueue.length) {
30 const [r, c] = endQueue.shift();
31 for (const [dr, dc] of this.directions) {
32 const nr = r + dr, nc = c + dc;
33 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromEnd[nr][nc] === Infinity) {
34 distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
35 endQueue.push([nr, nc]);
36 }
37 }
38 }
39
40 // Check overlap
41 for (let i = 0; i < n; ++i) {
42 for (let j = 0; j < n; ++j) {
43 if (distFromStart[i][j] !== Infinity && distFromEnd[i][j] !== Infinity) {
44 return distFromStart[i][j] + distFromEnd[i][j];
45 }
46 }
47 }
48 }
49
50 return -1;
51 }
52}
53
54const spf = new SafestPathFinder();
55const grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]];
56console.log(spf.bidirectionalSafenessFactor(grid)); // Output: Safeness factor
57The JavaScript interface executes bidirectional BFS starting from both ends, with simultaneous processing enhancing the invulnerability factor calculation through effective intersection detection.