<p>Given an <code>n x n</code> <code>grid</code>&nbsp;containing only values <code>0</code> and <code>1</code>, where&nbsp;<code>0</code> represents water&nbsp;and <code>1</code> 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 <code>-1</code>.</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/05/03/1336_ex1.JPG" style="width: 185px; height: 87px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,1],[0,0,0],[1,0,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The cell (1, 1) is as far as possible from all the land with distance 2.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/05/03/1336_ex2.JPG" style="width: 184px; height: 87px;" />
<pre>
<strong>Input:</strong> grid = [[1,0,0],[0,0,0],[0,0,0]]
<strong>Output:</strong> 4
<strong>Explanation:</strong> The cell (2, 2) is as far as possible from all the land with distance 4.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= n&nbsp;&lt;= 100</code></li>
	<li><code>grid[i][j]</code>&nbsp;is <code>0</code> or <code>1</code></li>
</ul>

class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        '''
        Approach:
        The problem requires finding the maximum distance from land (1) to the nearest water (0) in a grid. This is similar to the rotting oranges problem, where we perform a multi-source BFS (similar to Rotting Oranges Problem on Leetcode). Here, we treat all land cells (1s) as sources and propagate distances to water cells (0s) using BFS. The goal is to compute the maximum distance any water cell can be from the nearest land. If the grid is entirely land or entirely water, we return -1.
        '''
        
        # Get the dimensions of the grid
        rows = len(grid)
        cols = len(grid[0])

        # Directions for moving in the grid: right, left, down, up
        dir_x = [0, 0, 1, -1]
        dir_y = [1, -1, 0, 0]

        # To track visited cells to avoid revisiting them
        visited = [[False for _ in range(cols)] for _ in range(rows)]

        # Function to check if a position is valid within the grid
        def is_valid(row, col):
            # Check if the row and column are within bounds and not yet visited
            if row < 0 or col < 0 or row >= rows or col >= cols:
                return False
            elif visited[row][col] == True:
                return False
            else:
                return True

        # Initialize a deque (double-ended queue) to store BFS nodes
        q = deque()

        # BFS function to compute distances from land cells
        def bfs(q):
            max_dist = float('-inf')  # Initialize max distance to negative infinity
            while q:
                distance, curr_x, curr_y = q.popleft()  # Get the current node (cell) and its distance
                max_dist = max(max_dist, distance)  # Update the max distance

                # Explore all 4 possible directions (right, left, down, up)
                for k in range(4):
                    new_x = curr_x + dir_x[k]
                    new_y = curr_y + dir_y[k]

                    # Check if the new position is valid and is a water cell (0)
                    if is_valid(new_x, new_y) and grid[new_x][new_y] == 0 and visited[new_x][new_y] == False:
                        q.append((distance + 1, new_x, new_y))  # Add the new position with incremented distance to the queue
                        visited[new_x][new_y] = True  # Mark the new cell as visited

            return max_dist

        # Iterate through the grid to enqueue all land cells (1s) for multi-source BFS
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == 1:  # If it's land (1), add it as a source with distance 0
                    q.append((0, i, j))
                    visited[i][j] = True  # Mark land cells as visited since they are sources
                elif grid[i][j] == 0:
                    continue  # Skip water cells (0)
                else:
                    return -1  # Invalid input case (grid contains values other than 0 or 1)

        # Edge case: If there is no land at all or no water at all, return -1
        if len(q) == 0:  # No land found
            return -1
        
        if len(q) == rows * cols:  # Entire grid is land
            return -1

        # Perform BFS and get the maximum distance
        max_dist = bfs(q)

        return max_dist
473