Problem Statement:

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. If no land or water exists in the grid, return -1.

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|.

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.

Constraints:

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

Solution:

BFS is very appropriate here. We just need to check how many times we need to traverse to finish the queue of land cells. In one traversal, all adjacent members of the current queue get covered and converted to land cells.

 
class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) 
    {
        int n = grid.size(), distance=-1;
        queue<pair<int,int>> Q;
        for (int i=0; i<n; i++) for (int j=0; j<n; j++)
            if (grid[i][j]) Q.push({i,j});
        if (Q.empty()||Q.size()==n*n) return -1;//All water or all land
        vector<pair<int,int>> directions{ {-1,0},{1,0},{0,-1},{0,1} };
        while (!Q.empty())
        {
            for (int i=Q.size(); i>0; i--)
            {
                auto cell = Q.front();
                Q.pop();
                for (auto &dir: directions)
                {
                    int x = cell.first+dir.first;
                    int y = cell.second+dir.second;
                    if (x<0||x>=n||y<0||y>=n) continue;
                    if (grid[x][y]==0)
                    {
                        grid[x][y] = 1;
                        Q.push({x,y});
                    }
                }
            }
            distance++;
        }
        return distance;
    }
};