1162. As Far from Land as Possible

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

// BFS
int maxDistance(vector<vector<int>>& grid) { // time: O(n^2); space: O(n^2)
    const int n = grid.size();
    const vector<pair<int, int> > dirs({{-1, 0}, {1, 0}, {0, -1}, {0, 1}});
    queue<pair<int, int> > q;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (grid[i][j] == 1) {
                q.push({i, j});
            }
        }
    }
    int level = 0;
    while (!q.empty()) {
        ++level;
        for (int k = q.size() - 1; k >= 0; --k) {
            int r = q.front().first, c = q.front().second;
            q.pop();
            for (const pair<int, int>& dir : dirs) {
                int new_r = r + dir.first, new_c = c + dir.second;
                if (new_r < 0 || new_r >= n || new_c < 0 || new_c >= n || grid[new_r][new_c] != 0) continue;
                grid[new_r][new_c] = level + 1;
                q.push({new_r, new_c});
            }
        }
    }
    return level == 1 ? -1 : (level - 1);
}