Given an n x n grid&nbsp;containing only values 0 and 1, where&nbsp;0 represents water&nbsp;and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance.&nbsp;If no land or water exists in the grid, return -1.

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

&nbsp;
Example 1:

Input: grid = [[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: grid = [[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.


&nbsp;
Constraints:


	n == grid.length
	n == grid[i].length
	1 &lt;= n&nbsp;&lt;= 100
	grid[i][j]&nbsp;is 0 or 1


from collections import *
class Solution:
    def maxDistance(self, grid) -> int:
        m,n=len(grid),len(grid[0])
        queue=deque([])
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    queue.append((i,j))
        c=-1
        while queue:
            # print(queue)
            temp=len(queue)
            for _ in range(temp):
                (i,j)=queue.popleft()
                for (x,y) in ((i-1,j),(i+1,j),(i,j-1),(i,j+1)):
                    if x < 0 or x >= m or y < 0 or y >= n or grid[x][y]==1:
                        continue
                    grid[x][y]=1
                    queue.append((x,y))
            c+=1
        return c if c!=0 else -1
class Solution {
    class Point {
        int x, y;
        public Point(int x, int y){
            this.x=x;
            this.y=y;
        }
    }
    int[][] dist;
    int n,ans;
    int[] dx={0, 0, +1, -1};
    int[] dy={+1, -1, 0, 0};
    public int maxDistance(int[][] grid) {
        n=grid.length;
        dist = new int[n][n];
        Queue<Point> q = new LinkedList<>();
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if (grid[i][j]==0) dist[i][j]=2*1000*1000*1000;
                else {
                    dist[i][j]=0;
                    q.add(new Point(i, j)); // multisource on grid[i][j] = 1
                }
            }
        }
        ans=-1;
        while(!q.isEmpty()){
            Point p = q.poll();
            int x = p.x;
            int y = p.y;
            for (int k = 0; k < 4; k++) {
                int r=dx[k]+x;
                int c=dy[k]+y;
                if (valid(r,c)&&grid[r][c]==0&&dist[r][c]>dist[x][y]+1){
                    dist[r][c]=dist[x][y]+1;
                    Point newP = new Point(r,c);
                    q.add(newP);
                }
            }
        }
        for (int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                ans=Math.max(ans,dist[i][j]); // Manhattan distance is the same as the distance on the grid in general 
            }
        }
        if (ans==0||ans==2*1000*1000*1000) ans=-1;
        return ans;
    }
    public boolean valid(int r, int c){
        return r>=0&&c>=0&&r<n&&c<n;
    }
}
class Solution {
    vector<int> dr = {0,0,1,-1};
    vector<int> dc = {1,-1,0,0};
public:
    bool isPos(int r,int c,int n){
        return ( r>=0 && c>=0 && r<n && c<n );
    }

    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        vector< vector<int> > dist(n,vector<int>(n,-1));
        queue< vector<int> > pq;
        for(int i=0 ; i<n ; i++){
            for(int j=0 ; j<n ; j++){
                if( 1==grid[i][j] ){
                    dist[i][j] = 0;
                    pq.push({i,j});
                }
            }
        }
        int ans = 0;
        while( !pq.empty() ){
            vector<int> vect = pq.front();
            pq.pop();
            int r = vect[0];
            int c = vect[1];
            if( 0==grid[r][c] ){
                ans = max(ans,dist[r][c]);
            }
            for(int i=0 ; i<4 ; i++){
                int nr = r+dr[i];
                int nc = c+dc[i];
                if( isPos(nr,nc,n) && -1==dist[nr][nc] ){
                    dist[nr][nc] = dist[r][c]+1;
                    pq.push({nr,nc});
                }
            }
        }
        return (ans==0 ? -1 : ans);
    }
};
/**
 * @param {number[][]} grid
 * @return {number}
 */
const DIR = [
    [0,1],
    [0,-1],
    [1,0],
    [-1,0]
];
var maxDistance = function(grid) {
    const ROWS = grid.length;
    const COLS = grid[0].length;
    const cost = new Array(ROWS).fill().map(()=>new Array(COLS).fill(Infinity));
    const que = [];
    for(let row=0; row<ROWS; row++) {
        for(let col=0; col<COLS; col++) {
            if(grid[row][col] === 1) {
                que.push([row, col]);
                cost[row][col] = 0;
            }
        }
    }
    if(que.length == 0 || que.length == ROWS * COLS) return -1;
    while(que.length) {
        const [row, col] = que.shift();
        for(const dir of DIR) {
            const newRow = row+dir[0];
            const newCol = col+dir[1];
            if(newRow < 0 || newCol < 0 || newRow >= ROWS || newCol >= COLS) continue;
            if(cost[newRow][newCol] > cost[row][col] + 1) {
                cost[newRow][newCol] = cost[row][col] + 1;
                que.push([newRow, newCol]);
            }
        }
    }
    let max = 0;
    for(const row of cost) {
        max = Math.max(max, ...row);
    }
    return max;
};
As Far from Land as Possible