Method 1 - BFS + Dijkstra

We can use BFS to calculate the safeness factor for each cell in the grid, as BFS goes like a wave wise or level by level. We can create distances matrix for eg. 3 like this:

find-the-safest-path-in-a-grid-bfs-dijkstra-expl.excalidraw

Once, we have distances matrix, now we have to find path such that it's as far as possible from thief. For this we can simply choose to go at max distance cell starting from {0,0} using max heap. We can easily see, the nearest distance in this path from thief is 2. So, when adding the value in max heap, we add smallest safeness factor we have encountered so far. Once we have reach our destination, we return the smallest safeness factor.

Algorithm

Check if the start or end cell contains a thief. If so, return 0.
Do, multi-source BFS from the points of thief. We set the distance of all the safe nodes based on that.
Then we use max heap to find path with maximum safe distance. Track visited cells to avoid revisiting.
- Pop from the heap and check if we have reached destination. If so, return the safeness factor.
- Otherwise, for each neighbour, calculate the new safeness factor and push it into the heap for unvisited cells.
- This part is very similar to Dijkstra's algorithm to find shortest path

Video Explanation

1b:Tcb3,

Code

[{"language":"Java","code":"class Solution {\n\t// left, right, up, down\n    private static int[][] DIRS = new int[][]{{0,-1}, {0,1}, {-1,0}, {1,0}};\n\n    public int maximumSafenessFactor(List<List<Integer>> grid) {\n        int n = grid.size();\n\n\t\t// no path possible\n\t\tif (grid.get(0).get(0) == 1 || grid.get(n - 1).get(n - 1) == 1) {\n\t\t\treturn 0;\n\t\t}\n\t\t\n        int[][] distances = new int[n][n];\n\t\t\n\t\t// queue containing cell coordinates\n\t\tQueue<int[]> queue = new LinkedList<>();\n\t\t\n\t\t// initialize dist matrix and queue\n        for (int i = 0; i < n; i++) {\n            for (int j = 0; j < n; j++) {\n                if (grid.get(i).get(j) == 1) {\n\t                distances[i][j] = 0; // just for clarity\n                    queue.offer(new int[]{i, j});\n                } else {\n\t                distances[i][j] = -1;\n                }\n            }\n        }  \n     \n        // fill the distance matrix       \n        while(!queue.isEmpty()){\n\t        // we don't have to do bfs level by level\n\t        // as we are already storing scores in dist matrix\n\t        int[] cell = queue.poll();\n\t        int r = cell[0], c = cell[1];\n\t        for (int[] dir: DIRS) {\n\t\t        int newR = r + dir[0];\n\t\t        int newC = c + dir[1];\n\t\t        if (newR < 0 || newR >= n || newC < 0 || newC >= n || distances[newR][newC] != -1) {\n\t\t\t        continue;\n\t\t        }\n\t\t        distances[newR][newC] = distances[r][c] + 1;\n\t\t        queue.offer(new int[] {newR, newC});\n\t\t        \n\t        }\n        }\n        // maxHeap on distance matrix\n        PriorityQueue<int[]> maxHeap = new PriorityQueue<>((a, b) -> b[2] - a[2]);\n        maxHeap.add(new int[]{0, 0, distances[0][0]});\n        Set<String> visited = new HashSet<>();\n        visited.add(0 + \"--\" + 0);\n\n\t\twhile (!maxHeap.isEmpty()) {\n\t\t\tint[] cell = maxHeap.poll();\n\t\t\tint r = cell[0], c = cell[1], dist = cell[2];\n\t\t\tif (r == n - 1 && c == n - 1) {\n                return dist;\n            }\n\t\t\tfor (int[] dir: DIRS) {\n\t\t\t\tint newR = r + dir[0];\n\t\t        int newC = c + dir[1];\n\t\t\t\tString key = newR + \"--\" + newC;\n\t\t        if (newR < 0 || newR >= n || newC < 0 || newC >= n || visited.contains(key)) {\n\t\t\t        continue;\n\t\t        }\n\t\t        int safeDist = Math.min(dist, distances[newR][newC]);\n\t\t

Related Tags