Sponsored
Sponsored
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.
This 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.
1from collections import deque
2
3class SafestPathFinder:
4 def bidirectionalSafenessFactor(self, grid):
5 n = len(grid)
6 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
7 distFromStart = [[float('inf')] * n for _ in range(n)]
8 distFromEnd = [[float('inf')] * n for _ in range(n)]
9
10 qStart = deque([(0, 0)])
11 distFromStart[0][0] = 0
12
13 qEnd = deque([(n - 1, n - 1)])
14 distFromEnd[n - 1][n - 1] = 0
15
16 while qStart or qEnd:
17 if qStart:
18 r, c = qStart.popleft()
19 for dr, dc in directions:
20 nr, nc = r + dr, c + dc
21 if 0 <= nr < n and 0 <= nc < n and distFromStart[nr][nc] == float('inf'):
22 distFromStart[nr][nc] = distFromStart[r][c] + 1
23 qStart.append((nr, nc))
24
25 if qEnd:
26 r, c = qEnd.popleft()
27 for dr, dc in directions:
28 nr, nc = r + dr, c + dc
29 if 0 <= nr < n and 0 <= nc < n and distFromEnd[nr][nc] == float('inf'):
30 distFromEnd[nr][nc] = distFromEnd[r][c] + 1
31 qEnd.append((nr, nc))
32
33 for i in range(n):
34 for j in range(n):
35 if distFromStart[i][j] != float('inf') and distFromEnd[i][j] != float('inf'):
36 return distFromStart[i][j] + distFromEnd[i][j]
37
38 return -1
39
40# Example usage
41spf = SafestPathFinder()
42grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]]
43print(spf.bidirectionalSafenessFactor(grid)) # Output: Safeness factor
44The Python solution deploys bidirectional BFS to handle both source and target expansions concurrently. This not only improves exploration efficiency but also allows quicker discovery of overlapping safe paths.