2812

FindTheSafest.java

class Solution {
    class Step {
        int x;
        int y;
        int level;
        Step(int x, int y) {
            this.x = x;
            this.y = y;
        }
        Step(int x, int y, int level) {
            this.x = x;
            this.y = y;
            this.level = level;
        }
    }
    private static final int[][] DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int m = grid.size();
        int n = grid.get(0).size();

        if (grid.get(0).get(0) == 1|| grid.get(m-1).get(n-1) == 1) {
            return 0;
        }
        
        // cal theif dist first
        // boolean[][] visited = new boolean[m][n];
        Queue<Step> queue = new LinkedList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    queue.offer(new Step(i, j, 1));
                }
            }
        }
        
        int maxLevel = 0;
        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            
            for (int[] dir : DIRECTIONS) {
                int x = cur.x + dir[0];
                int y = cur.y + dir[1];
                if (x < 0 || x >= m || y < 0 || y >= n || grid.get(x).get(y) != 0) { // we want to fill 0 now
                    continue;
                }
                queue.offer(new Step(x, y, cur.level+1));
                grid.get(x).set(y, cur.level+1);
                maxLevel = cur.level+1;
            }
        }

        int left = 0;
        int right = maxLevel;
        while (left <= right) {
            int mid = left + (right - left)/2;
            if (isDistSafe(mid, grid)) {
                if (isDistSafe(mid+1, grid) && mid+1 < maxLevel) {
                    left = mid + 1;
                } else {
                    return mid;
                }
            } else {
                right = mid - 1;
            }
        }
        return 0;
    }

    private boolean isDistSafe(int dist, List<List<Integer>> grid) {
        if (grid.get(0).get(0) <= dist) { // if in the beginning, it's not to add in queue and do BFS, return false
            return false;
        }

        int m = grid.size();
        int n = grid.get(0).size();

        Queue<Step> queue = new LinkedList<>();
        boolean[][] visited = new boolean[m][n];
        queue.offer(new Step(0, 0));

        while (!queue.isEmpty()) {
            Step cur = queue.poll();

            if (visited[cur.x][cur.y]) {
                continue;
            }
            visited[cur.x][cur.y] = true;
            if (cur.x == m - 1 && cur.y == n - 1) {
                return true;
            }

            for (int[] dir : DIRECTIONS) {
                int x = cur.x + dir[0];
                int y = cur.y + dir[1];
                if (x < 0 || x >= m || y < 0 || y >= n || grid.get(x).get(y) <= dist) {
                    continue;
                }

                queue.offer(new Step(x, y));
            }
        }
        return false;
    }
}