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.
The 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.
1import java.util.*;
2
3public class SafestPathFinder {
4 private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
5
6 public int bidirectionalSafenessFactor(int[][] grid) {
7 int n = grid.length;
8 int[][] distFromStart = new int[n][n];
9 int[][] distFromEnd = new int[n][n];
10 for (int[] row : distFromStart) Arrays.fill(row, Integer.MAX_VALUE);
11 for (int[] row : distFromEnd) Arrays.fill(row, Integer.MAX_VALUE);
12
13 Queue<int[]> startQueue = new LinkedList<>();
14 startQueue.offer(new int[]{0, 0});
15 distFromStart[0][0] = 0;
16
17 Queue<int[]> endQueue = new LinkedList<>();
18 endQueue.offer(new int[]{n - 1, n - 1});
19 distFromEnd[n - 1][n - 1] = 0;
20
21 while (!startQueue.isEmpty() || !endQueue.isEmpty()) {
22 if (!startQueue.isEmpty()) {
23 int[] pos = startQueue.poll();
24 int r = pos[0], c = pos[1];
25 for (int[] dir : directions) {
26 int nr = r + dir[0], nc = c + dir[1];
27 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distFromStart[nr][nc] == Integer.MAX_VALUE) {
28 distFromStart[nr][nc] = distFromStart[r][c] + 1;
29 startQueue.offer(new int[]{nr, nc});
30 }
31 }
32 }
33
34 if (!endQueue.isEmpty()) {
35 int[] pos = endQueue.poll();
36 int r = pos[0], c = pos[1];
37 for (int[] 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] == Integer.MAX_VALUE) {
40 distFromEnd[nr][nc] = distFromEnd[r][c] + 1;
41 endQueue.offer(new int[]{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] != Integer.MAX_VALUE && distFromEnd[i][j] != Integer.MAX_VALUE) {
50 return distFromStart[i][j] + distFromEnd[i][j];
51 }
52 }
53 }
54 }
55
56 return -1;
57 }
58
59 public static void main(String[] args) {
60 SafestPathFinder spf = new SafestPathFinder();
61 int[][] grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
62 System.out.println(spf.bidirectionalSafenessFactor(grid)); // Output: Safeness factor
63 }
64}
65The Java implementation employs bidirectional BFS from starting and ending corners, advancing until they converge. This optimized strategy minimizes redundant explorations and uncovers shared safe paths effectively.