LeetCode [1162] As Far from Land as Possible

1162. As Far from Land as Possible

Medium

Given an N x N grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.

The distance used in this problem is the Manhattan distance: the distance between two cells (x0, y0) and (x1, y1) is |x0 - x1| + |y0 - y1|.

If no land or water exists in the grid, return -1.

 

Example 1:

Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation: 
The cell (1, 1) is as far as possible from all the land with distance 2.

Example 2:

Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation: 
The cell (2, 2) is as far as possible from all the land with distance 4.

 

Note:

1. 1 <= grid.length == grid[0].length <= 100
2. grid[i][j] is 0 or 1

class Solution {
    int[][] dir = new int[][]{{-1,0},{1,0},{0,-1},{0,1}};
    public int maxDistance(int[][] grid) {
        int ret = 0;
        int m = grid.length, n = grid[0].length;
        Queue<int[]> que = new ArrayDeque<>();
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
                if(grid[i][j]==1)
                    que.add(new int[]{i, j});
            }
        }

        int step = -1;
        while(!que.isEmpty()){
            ret = Math.max(ret, (++step));
            int sz = que.size();
            for(int i=0; i<sz; ++i){
                int[] p = que.poll();
                for(int[] d : dir){
                    int x = p[0]+d[0], y = p[1]+d[1];
                    if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==0){
                        grid[x][y] = -1;//visited 0
                        que.add(new int[]{x, y});
                    }
                }
            }
        }
        return ret==0?-1:ret;
    }
}