1162. As Far from Land as Possible

https://leetcode.com/problems/as-far-from-land-as-possible/

Runtime: O(n * n). We process an individual cell only once (or twice).

Memory: O(n) for the queue.

1. 從陸地出發, 會比較快, 所以是 offer 1 進去

2. distance 要從 -1 開始計算

3. 剩下跟 200差不多, 只是多了queue

4. 算過的給2 (給1也可以, 只是會比較沒問題

class Solution {
    int dirs[][] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int maxDistance(int[][] grid) {
        
        if (grid == null) {
            return 0;
        }
        int n = grid.length;

        // bfs
        // queue
        Queue<int[]> q = new ArrayDeque<>();
        // n^2
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) { // from land
                   q.offer(new int[]{i, j}); 
                }
            }
        }
        
        if (q.isEmpty() || q.size() == n*n) {
            return -1;
        }
        
        int distance = -1;
        while (!q.isEmpty()) {
            distance++;
            int levels = q.size();
            
            for (int i = 0; i < levels; i++) {
                int node[] = q.poll();
                int r = node[0];
                int c = node[1];
                for (int[] d : dirs) {
                    int r0 = r + d[0];
                    int c0 = c + d[1];
                    if (inArea(r0, c0, grid) && grid[r0][c0] == 0) {
                        grid[r0][c0] = 2;
                        q.offer(new int[]{r0, c0});
                    }
                }
            }
        }
        return distance;
    }
    
    private boolean inArea(int r, int c, int[][] grid) {
        return (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length);
    }
}