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 <= grid.length == grid[0].length <= 100
grid[i][j] is 0 or 1
from queue import PriorityQueue

class Solution:
    def isInRange(self, grid, x, y):
        return (0 <= x and x < len(grid[0])) and (0 <= y and y < len(grid))

    def maxDistance(self, grid: List[List[int]]) -> int:
        q = PriorityQueue()
        visited = dict()
        maxDist = 0
        toVisit = [(-1, 0), (0, 0), (1, 0), (0, 1), (0, -1)]
        
        for x, i in enumerate(grid):
            for y, j in enumerate(i):
                if j is not 0:
                    q.put((0, (x, y)))
                    visited[(x, y)] = True
                    
        if (q.qsize() >= len(grid[0]) * len(grid) or q.qsize() is 0):
            return -1
                    
        while not q.empty():
            item = q.get()
            maxDist = max(maxDist, item[0])
            
            for p in toVisit:
                x = p[0] + item[1][0]
                y = p[1] + item[1][1]
                
                if self.isInRange(grid, x, y) and visited.get((x, y)) is not True:
                    visited[(x, y)] = True
                    q.put((item[0] + 1, (x, y)))
            
        return maxDist
from queue import PriorityQueue

class Solution:
    def isInRange(self, grid, x, y):
        return (0 <= x and x < len(grid[0])) and (0 <= y and y < len(grid))

    def maxDistance(self, grid: List[List[int]]) -> int:
        q = PriorityQueue()
        visited = dict()
        maxDist = 0
        toVisit = [(-1, 0), (0, 0), (1, 0), (0, 1), (0, -1)]
        
        for x, i in enumerate(grid):
            for y, j in enumerate(i):
                if j is not 0:
                    q.put((0, (x, y)))
                    visited[(x, y)] = True
                    
        if (q.qsize() >= len(grid[0]) * len(grid) or q.qsize() is 0):
            return -1
                    
        while not q.empty():
            item = q.get()
            maxDist = max(maxDist, item[0])
            
            for p in toVisit:
                x = p[0] + item[1][0]
                y = p[1] + item[1][1]
                
                if self.isInRange(grid, x, y) and visited.get((x, y)) is not True:
                    visited[(x, y)] = True
                    q.put((item[0] + 1, (x, y)))
            
        return maxDist