# 2812. Find the Safest Path in a Grid

````java
```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)
```

```java
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)
 */
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/2812.-find-the-safest-path-in-a-grid.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.