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 java.util.*;
2
3public class SafestPathFinder {
4 private static final int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
5
6 public int maxSafenessFactor(int[][] grid) {
7 int n = grid.length;
8 int[][] distance = new int[n][n];
9 for (int[] row : distance) Arrays.fill(row, Integer.MAX_VALUE);
10 Queue<int[]> queue = new LinkedList<>();
11
12 // BFS to calculate distance to the nearest thief
13 for (int r = 0; r < n; r++) {
14 for (int c = 0; c < n; c++) {
15 if (grid[r][c] == 1) {
16 queue.offer(new int[]{r, c});
17 distance[r][c] = 0;
18 }
19 }
20 }
21
22 while (!queue.isEmpty()) {
23 int[] pos = queue.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 && distance[nr][nc] == Integer.MAX_VALUE) {
28 distance[nr][nc] = distance[r][c] + 1;
29 queue.offer(new int[]{nr, nc});
30 }
31 }
32 }
33
34 // Max-heap-like Dijkstra's for the safest path
35 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[2] - a[2]); // Max-heap based on safeness factor
36 pq.offer(new int[]{0, 0, distance[0][0]});
37 boolean[][] visited = new boolean[n][n];
38
39 while (!pq.isEmpty()) {
40 int[] cur = pq.poll();
41 int r = cur[0], c = cur[1], safeness = cur[2];
42
43 if (r == n - 1 && c == n - 1) return safeness;
44 visited[r][c] = true;
45
46 for (int[] dir : directions) {
47 int nr = r + dir[0], nc = c + dir[1];
48 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
49 int newSafeness = Math.min(safeness, distance[nr][nc]);
50 pq.offer(new int[]{nr, nc, newSafeness});
51 }
52 }
53 }
54
55 return 0;
56 }
57
58 public static void main(String[] args) {
59 SafestPathFinder spf = new SafestPathFinder();
60 int[][] grid = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
61 System.out.println(spf.maxSafenessFactor(grid)); // Output: 2
62 }
63}
64The Java implementation uses BFS to compute how far each cell is from the closest thief, followed by priority-based processing to ensure optimal safeness to the target using Dijkstra's inspired strategy.
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.