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.
1import heapq
2
3class SafestPathFinder:
4 def maxSafenessFactor(self, grid):
5 n = len(grid)
6 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
7 distance = [[float('inf')] * n for _ in range(n)]
8 q = []
9
10 # BFS from all thieves
11 for r in range(n):
12 for c in range(n):
13 if grid[r][c] == 1:
14 q.append((r, c))
15 distance[r][c] = 0
16
17 for r, c in q:
18 for dr, dc in directions:
19 nr, nc = r + dr, c + dc
20 if 0 <= nr < n and 0 <= nc < n and distance[nr][nc] == float('inf'):
21 distance[nr][nc] = distance[r][c] + 1
22 q.append((nr, nc))
23
24 # Max-safeness factor using a max-heap
25 heap = [(-distance[0][0], 0, 0)] # store as negative for max-heap behavior
26 maxSafeness = [[-1] * n for _ in range(n)]
27 maxSafeness[0][0] = distance[0][0]
28
29 while heap:
30 safeness, r, c = heapq.heappop(heap)
31 safeness = -safeness
32
33 for dr, dc in directions:
34 nr, nc = r + dr, c + dc
35 if 0 <= nr < n and 0 <= nc < n:
36 newSafeness = min(safeness, distance[nr][nc])
37 if newSafeness > maxSafeness[nr][nc]:
38 maxSafeness[nr][nc] = newSafeness
39 heapq.heappush(heap, (-newSafeness, nr, nc))
40
41 return maxSafeness[n-1][n-1]
42
43# Example usage
44spf = SafestPathFinder()
45grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]]
46print(spf.maxSafenessFactor(grid)) # Output: 2
47The Python solution uses BFS to precompute distances from all thieves. Then, a max-heap (prioritizing higher safeness) guides traversal from the start to the end, ensuring the net max safeness factor is achieved.
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.
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 BidirectionalSafenessFactor(int[][] grid) {
13 int n = grid.Length;
14 int[][] distFromStart = new int[n][];
15 int[][] distFromEnd = new int[n][];
16 for (int i = 0; i < n; i++) {
17 distFromStart[i] = new int[n];
18 distFromEnd[i] = new int[n];
19 Array.Fill(distFromStart[i], int.MaxValue);
20 Array.Fill(distFromEnd[i], int.MaxValue);
21 }
22
23 Queue<(int, int)> startQueue = new();
24 startQueue.Enqueue((0, 0));
25 distFromStart[0][0] = 0;
26
27 Queue<(int, int)> endQueue = new();
28 endQueue.Enqueue((n - 1, n - 1));
29 distFromEnd[n - 1][n - 1] = 0;
30
31 while (startQueue.Count > 0 || endQueue.Count > 0) {
32 if (startQueue.Count > 0) {
33 var (r, c) = startQueue.Dequeue();
34 foreach (var dir in directions) {
35 int nr = r + dir[0];
36 int nc = c + dir[1];
37 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] == int.MaxValue) {
38 distFromStart[nr][nc] = distFromStart[r][c] + 1;
39 startQueue.Enqueue((nr, nc));
40 }
41 }
42 }
43
44 if (endQueue.Count > 0) {
45 var (r, c) = endQueue.Dequeue();
46 foreach (var dir in directions) {
47 int nr = r + dir[0];
48 int nc = c + dir[1];
49 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromEnd[nr][nc] == int.MaxValue) {
50 distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
51 endQueue.Enqueue((nr, nc));
52 }
53 }
54 }
55
56 // Check overlapping
57data switching
58 for (int i = 0; i < n; ++i) {
59 for (int j = 0; j < n; ++j) {
60 if (distFromStart[i][j] != int.MaxValue && distFromEnd[i][j] != int.MaxValue) {
61 return distFromStart[i][j] + distFromEnd[i][j];
62 }
63 }
64 }
65 }
66
67 return -1;
68 }
69
70 public static void Main() {
71 SafestPathFinder spf = new();
72 int[][] grid = new int[][] {
73 new int[] { 0, 0, 1 },
74 new int[] { 0, 0, 0 },
75 new int[] { 0, 0, 0 }
76 };
77 Console.WriteLine(spf.BidirectionalSafenessFactor(grid)); // Output: Safeness factor
78 }
79}
80The C# method leverages bidirectional BFS to concurrently expand from both initial and final cell locations until intersection occurs. It's highly efficient in discovering paths by reducing each direction BFS depth.