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.
1using System;
2using System.Collections.Generic;
3
4public class SafestPathFinder {
5 private static int[][] directions = new int[4][] {
6 new int[] { 0, 1 },
7 new int[] { 1, 0 },
8 new int[] { 0, -1 },
9 new int[] { -1, 0 }
10 };
11
12 public int MaxSafenessFactor(int[][] grid) {
13 int n = grid.Length;
14 int[][] distance = new int[n][];
15 for (int i = 0; i < n; i++)
16 distance[i] = new int[n];
17
18 for (int i = 0; i < n; i++)
19 for (int j = 0; j < n; j++)
20 distance[i][j] = int.MaxValue;
21
22 Queue<(int, int)> queue = new Queue<(int, int)>();
23
24 for (int r = 0; r < n; r++) {
25 for (int c = 0; c < n; c++) {
26 if (grid[r][c] == 1) {
27 queue.Enqueue((r, c));
28 distance[r][c] = 0;
29 }
30 }
31 }
32
33 while (queue.Count > 0) {
34 var (r, c) = queue.Dequeue();
35 foreach (var dir in directions) {
36 int nr = r + dir[0];
37 int nc = c + dir[1];
38 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distance[nr][nc] == int.MaxValue) {
39 distance[nr][nc] = distance[r][c] + 1;
40 queue.Enqueue((nr, nc));
41 }
42 }
43 }
44
45 PriorityQueue<(int, int, int)> pq = new();
46 pq.Enqueue((0, 0, distance[0][0]));
47 bool[,] visited = new bool[n, n];
48
49 while (pq.Count > 0) {
50 var (r, c, safeness) = pq.Dequeue();
51 if (r == n - 1 && c == n - 1) return safeness;
52 if (visited[r, c]) continue;
53 visited[r, c] = true;
54
55 foreach (var dir in directions) {
56 int nr = r + dir[0];
57 int nc = c + dir[1];
58 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr, nc]) {
59 int newSafeness = Math.Min(safeness, distance[nr][nc]);
60 pq.Enqueue((nr, nc, newSafeness));
61 }
62 }
63 }
64
65 return 0;
66 }
67
68 public static void Main() {
69 SafestPathFinder spf = new SafestPathFinder();
70 int[][] grid = new int[][] {
71 new int[] { 0, 0, 1 },
72 new int[] { 0, 0, 0 },
73 new int[] { 0, 0, 0 }
74 };
75 Console.WriteLine(spf.MaxSafenessFactor(grid)); // Output: 2
76 }
77}
78
79public class PriorityQueue<T> where T : IComparable<T> {
80 private List<T> data = new List<T>();
81
82 public int Count => data.Count;
83
84 public void Enqueue(T item) {
85 data.Add(item);
86 int ci = data.Count - 1;
87 while (ci > 0) {
88 int pi = (ci - 1) / 2;
89 if (data[ci].CompareTo(data[pi]) <= 0) break;
90 var tmp = data[ci];
91 data[ci] = data[pi];
92 data[pi] = tmp;
93 ci = pi;
94 }
95 }
96
97 public T Dequeue() {
98 var ret = data[0];
99 var li = data.Count - 1;
100 data[0] = data[li];
101 data.RemoveAt(li);
102 --li;
103 int pi = 0;
104 while (true) {
105 int ci = pi * 2 + 1;
106 if (ci > li) break;
107 int rc = ci + 1;
108 if (rc <= li && data[rc].CompareTo(data[ci]) > 0) ci = rc;
109 if (data[pi].CompareTo(data[ci]) >= 0) break;
110 var tmp = data[pi];
111 data[pi] = data[ci];
112 data[ci] = tmp;
113 pi = ci;
114 }
115 return ret;
116 }
117}
118The C# solution begins by performing BFS to calculate the distance from every cell to the nearest thief. After that, it implements a version of Dijkstra’s algorithm to efficiently find the path maximizing safeness from the start to the endpoint.
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.