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.
1class SafestPathFinder {
2 constructor() {
3 this.directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
4 }
5
6 maxSafenessFactor(grid) {
7 const n = grid.length;
8 const distance = Array.from({ length: n }, () => Array(n).fill(Infinity));
9 const queue = [];
10
11 for (let r = 0; r < n; r++) {
12 for (let c = 0; c < n; c++) {
13 if (grid[r][c] === 1) {
14 queue.push([r, c]);
15 distance[r][c] = 0;
16 }
17 }
18 }
19
20 let idx = 0;
21 while (idx < queue.length) {
22 const [r, c] = queue[idx++];
23 for (const [dr, dc] of this.directions) {
24 const nr = r + dr, nc = c + dc;
25 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distance[nr][nc] === Infinity) {
26 distance[nr][nc] = distance[r][c] + 1;
27 queue.push([nr, nc]);
28 }
29 }
30 }
31
32 const heap = new MaxPriorityQueue({ priority: x => x[2] });
33 heap.enqueue([0, 0, distance[0][0]]);
34
35 const visited = Array.from({ length: n }, () => Array(n).fill(false));
36
37 while (!heap.isEmpty()) {
38 const { element: [r, c, safeness] } = heap.dequeue();
39 if (r === n - 1 && c === n - 1) return safeness;
40 if (visited[r][c]) continue;
41 visited[r][c] = true;
42
43 for (const [dr, dc] of this.directions) {
44 const nr = r + dr, nc = c + dc;
45 if (nr >= 0 && nr < n && nc >= 0 && nc < n && !visited[nr][nc]) {
46 const newSafeness = Math.min(safeness, distance[nr][nc]);
47 heap.enqueue([nr, nc, newSafeness]);
48 }
49 }
50 }
51 return 0;
52 }
53}
54
55const spf = new SafestPathFinder();
56const grid = [[0, 0, 1], [0, 0, 0], [0, 0, 0]];
57console.log(spf.maxSafenessFactor(grid)); // Output: 2
58JavaScript solution leverages a BFS to determine distances from each grid cell to thieves, followed by a priority-based strategy using a max-heap to compile the path with the greatest safeness factor.
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 <stdio.h>
2#include <stdlib.h>
3#include <limits.h>
4#include <stdbool.h>
5#include <string.h>
6
7#define MAX 400
8
9int grid[MAX][MAX];
10int n;
11
12int direction[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
13
14int bidirectionalSafenessFactor(int grid[][MAX], int n) {
15 // Distance from start and end
16 int distanceStart[MAX][MAX];
17 int distanceEnd[MAX][MAX];
18
19 memset(distanceStart, INT_MAX, sizeof(distanceStart));
20 memset(distanceEnd, INT_MAX, sizeof(distanceEnd));
21
22 // BFS start queue
23 int queueStart[MAX*MAX][2];
24 int frontStart = 0, rearStart = 0;
25
26 queueStart[rearStart][0] = 0;
27 queueStart[rearStart][1] = 0;
28 rearStart++;
29 distanceStart[0][0] = 0;
30
31 // BFS end queue
32 int queueEnd[MAX*MAX][2];
33 int frontEnd = 0, rearEnd = 0;
34
35 queueEnd[rearEnd][0] = n-1;
36 queueEnd[rearEnd][1] = n-1;
37 rearEnd++;
38 distanceEnd[n-1][n-1] = 0;
39
40 while (frontStart < rearStart && frontEnd < rearEnd) {
41 // Expand from start
42 int r = queueStart[frontStart][0], c = queueStart[frontStart][1];
43 frontStart++;
44
45 for (int d = 0; d < 4; ++d) {
46 int nr = r + direction[d][0], nc = c + direction[d][1];
47 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distanceStart[nr][nc] == INT_MAX) {
48 distanceStart[nr][nc] = distanceStart[r][c] + 1;
49 queueStart[rearStart][0] = nr;
50 queueStart[rearStart][1] = nc;
51 rearStart++;
52 }
53 }
54
55 // Expand from end
56 r = queueEnd[frontEnd][0], c = queueEnd[frontEnd][1];
57 frontEnd++;
58
59 for (int d = 0; d < 4; ++d) {
60 int nr = r + direction[d][0], nc = c + direction[d][1];
61 if (nr >= 0 && nr < n && nc >= 0 && nc < n && distanceEnd[nr][nc] == INT_MAX) {
62 distanceEnd[nr][nc] = distanceEnd[r][c] + 1;
63 queueEnd[rearEnd][0] = nr;
64 queueEnd[rearEnd][1] = nc;
65 rearEnd++;
66 }
67 }
68
69 // Check overlap
70 for (int i = 0; i < n; ++i) {
71 for (int j = 0; j < n; ++j) {
72 if (distanceStart[i][j] != INT_MAX && distanceEnd[i][j] != INT_MAX) {
73 return distanceStart[i][j] + distanceEnd[i][j];
74 }
75 }
76 }
77 }
78
79 return -1;
80}
81
82int main() {
83 int gridExample[MAX][MAX] = {{0, 0, 1}, {0, 0, 0}, {0, 0, 0}};
84 int n = 3;
85 printf("%d\n", bidirectionalSafenessFactor(gridExample, n));
86 return 0;
87}
88The C solution processes the grid using bidirectional BFS starting from both the top-left corner and the bottom-right corner simultaneously, aiming to explore overlapping paths and maximize their safeness factor.