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 <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4#include <stdbool.h>
5#include <string.h>
6
7#define MAX 400
8
9int grid[MAX][MAX];
10int n;
11
12int direction[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
13
14int maxSafenessFactor(int grid[][MAX], int n) {
15 int distance[MAX][MAX];
16 bool visited[MAX][MAX];
17 memset(distance, INT_MAX, sizeof(distance));
18 memset(visited, false, sizeof(visited));
19
20 // BFS for shortest distance from any thief
21 int qsize = n * n;
22 int queue[qsize][2];
23 int front = 0, rear = 0;
24
25 for(int r = 0; r < n; ++r){
26 for(int c = 0; c < n; ++c){
27 if(grid[r][c] == 1) {
28 queue[rear][0] = r;
29 queue[rear][1] = c;
30 rear++;
31 distance[r][c] = 0;
32 visited[r][c] = true;
33 }
34 }
35 }
36
37 while (front < rear) {
38 int r = queue[front][0], c = queue[front][1];
39 front++;
40 for (int d = 0; d < 4; ++d) {
41 int nr = r + direction[d][0], nc = c + direction[d][1];
42 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
43 visited[nr][nc] = true;
44 distance[nr][nc] = distance[r][c] + 1;
45 queue[rear][0] = nr;
46 queue[rear][1] = nc;
47 rear++;
48 }
49 }
50 }
51
52 // Use Dijkstra's rather than simple BFS from (0, 0) due to distance
53 int maxSafeness[MAX][MAX];
54 int pq[qsize][3];
55 int pqSize = 0;
56
57 bool used[MAX][MAX];
58 memset(used, false, sizeof(used));
59
60 // Initialize dijkstra's variables
61 memset(maxSafeness, -1, sizeof(maxSafeness));
62 maxSafeness[0][0] = distance[0][0];
63 pq[pqSize][0] = 0, pq[pqSize][1] = 0, pq[pqSize][2] = distance[0][0];
64 pqSize++;
65
66 while (pqSize > 0) {
67 // Extract the node with maximum safeness factor
68 int maxDistIndex = -1;
69 for (int i = 0; i < pqSize; i++) {
70 if (maxDistIndex == -1 || pq[i][2] > pq[maxDistIndex][2]) {
71 maxDistIndex = i;
72 }
73 }
74
75 int curR = pq[maxDistIndex][0], curC = pq[maxDistIndex][1];
76 int curD = pq[maxDistIndex][2];
77
78 // Remove from queue
79 for (int i = maxDistIndex; i < pqSize - 1; i++) {
80 pq[i][0] = pq[i+1][0];
81 pq[i][1] = pq[i+1][1];
82 pq[i][2] = pq[i+1][2];
83 }
84 pqSize--;
85
86 if (used[curR][curC]) continue;
87 used[curR][curC] = true;
88
89 for (int d = 0; d < 4; ++d) {
90 int nr = curR + direction[d][0], nc = curC + direction[d][1];
91 if (nr >= 0 && nr < n && nc >= 0 && nc < n) {
92 if (min(curD, distance[nr][nc]) > maxSafeness[nr][nc]) {
93 maxSafeness[nr][nc] = min(curD, distance[nr][nc]);
94 pq[pqSize][0] = nr;
95 pq[pqSize][1] = nc;
96 pq[pqSize][2] = maxSafeness[nr][nc];
97 pqSize++;
98 }
99 }
100 }
101 }
102
103 return maxSafeness[n-1][n-1];
104}
105
106int main() {
107 int gridExample[MAX][MAX] = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
108 int n = 3;
109 printf("%d\n", maxSafenessFactor(gridExample, n));
110 return 0;
111}
112This C solution first performs a BFS from all thief positions to calculate the distance from each cell to the nearest thief. Then, it uses Dijkstra-like processing to find the maximum safeness from the top-left corner to the bottom-right corner.
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.
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}
64The C++ code takes advantage of bidirectional BFS where BFS expansions occur simultaneously from both the beginning and ending points on the grid. This often reduces the depth of expansion and uncovers maximum converging safeness factors more rapidly.