2812. Find the Safest Path in a Grid

```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;
    }
}
```

latest one:

1. T: O(n^2)
2. T: O(n^2logn)
so total is O(n^2logn)

S: O(n^2)

class Solution {
    private record Step(int x, int y, int level){};
    private record Position(int x, int y){};

    private static final int[][] DIRECTIONS = {{0,1}, {1,0}, {0,-1}, {-1,0}};

    public int maximumSafenessFactor(List<List<Integer>> grid) {
        int n = grid.size();
        int[][] score = bfs1(grid);

        int result = 0;

        // binary search to find max safe factor
        int left = 0;
        int right = 2*n; // max is at most 2n
        while (left <= right) {
            int mid = left + (right - left)/2;

            if (isSafe(mid, score)) { // try larger
                if (mid + 1 <= 2*n && isSafe(mid+1, score)) { // because we always want larger, so only here need to do
                    left = mid + 1;
                } else {
                    return mid;
                }
            } else {
                right = mid - 1;
            }
            result = Math.max(result, mid);
        }
        return result;
    }
    // 1. build a safe_score matrix for later to use (BFS, like 01-matrix)
    private int[][] bfs1(List<List<Integer>> grid) {
        int n = grid.size();
        int[][] score = new int[n][n];

        Queue<Step> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid.get(i).get(j) == 1) {
                    queue.offer(new Step(i, j, 1));
                }
            }
        }

        while (!queue.isEmpty()) {
            Step cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            int level = cur.level;
            if (x < 0 || x >= n || y < 0 || y >= n || score[x][y] != 0) {
                continue;
            }

            score[x][y] = level;
            for (int[] dir : DIRECTIONS) {
                queue.offer(new Step(x + dir[0], y + dir[1], level+1));
            }
        }
        return score;
    }
    // 3. inside binary search, if this safeness factor can walk from 0,0 to n-1,n-1 (BFS), means it's ok
    private boolean isSafe(int dist, int[][] score) {
        if (score[0][0] <= dist) { // start point is not ok, return false;
            return false;
        }
        int n = score.length;
        Queue<Position> queue = new LinkedList<>();
        queue.offer(new Position(0, 0));
        boolean[][] visited = new boolean[n][n];

        while (!queue.isEmpty()) {
            Position cur = queue.poll();
            int x = cur.x;
            int y = cur.y;
            if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y] || score[x][y] <= dist) {
                continue;
            }
            visited[x][y] = true;
            if (x == n-1 && y == n-1) {
                return true;
            }
            
            for (int[] dir : DIRECTIONS) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                queue.offer(new Position(nx, ny));
            }
        }
        return false;
    }
}


/**
1. build a safe_score matrix for later to use (BFS, like 01matrix)
2. use binary search 0 ~ 2n to find a safeness factor
3. inside binary search, if this safeness factor can walk from 0,0 to n-1,n-1 (BFS), means it's ok
so we can try to find larger in bs
or find smaller in bs

1. T: O(n^2)
2. T: O(n^2logn)
so total is O(n^2logn)

S: O(n^2)
 */