2812. Find the Safest Path in a Grid

2812. Find the Safest Path in a Grid.java

import java.util.*;

public class Solution {
    
    private int nr, nc;

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        nr = grid.size();
        nc = grid.get(0).size();
        
        int[][] minDists = new int[nr][nc];
        for (int[] row : minDists) {
            Arrays.fill(row, Integer.MAX_VALUE);
        }
        
        getMinDistFromT(minDists, grid);
        return findPath(minDists);
    }

    private void getMinDistFromT(int[][] minDists, List<List<Integer>> grid) {
        Queue<int[]> q = new LinkedList<>();
        
        for (int r = 0; r < nr; r++) {
            for (int c = 0; c < nc; c++) {
                if (grid.get(r).get(c) == 1) {
                    q.add(new int[]{r, c, 0});
                    minDists[r][c] = 0;
                }
            }
        }
        
        while (!q.isEmpty()) {
            int[] cell = q.poll();
            int r = cell[0], c = cell[1], dist = cell[2];
            
            for (int[] d : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
                int r_nx = r + d[0], c_nx = c + d[1];
                
                if (r_nx < 0 || r_nx >= nr || c_nx < 0 || c_nx >= nc || minDists[r_nx][c_nx] != Integer.MAX_VALUE) {
                    continue;
                }
                
                q.add(new int[]{r_nx, c_nx, dist + 1});
                minDists[r_nx][c_nx] = dist + 1;
            }
        }
    }
    
    private boolean canReach(int r, int c, int distTarget, int[][] minDists, boolean[][] visited) {
        if (visited[r][c]) {
            return false;
        }
        visited[r][c] = true;
        if (minDists[r][c] < distTarget) {
            return false;
        }
        if (r == nr - 1 && c == nc - 1) {
            return true;
        }
        
        for (int[] d : new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}) {
            int r_nx = r + d[0], c_nx = c + d[1];
            
            if (r_nx < 0 || r_nx >= nr || c_nx < 0 || c_nx >= nc) {
                continue;
            }
            
            if (canReach(r_nx, c_nx, distTarget, minDists, visited)) {
                return true;
            }
        }
        
        return false;
    }

    private int findPath(int[][] minDists) {
        int l = 0, r = nr + nc;
        int distMax = 0;
        
        while (l <= r) {
            int m = (l + r) / 2;
            
            boolean[][] visited = new boolean[nr][nc];
            if (canReach(0, 0, m, minDists, visited)) {
                distMax = Math.max(distMax, m);
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        
        return distMax;
    }
}