> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/dfs-and-bfs/1162.-as-far-from-land-as-possible.md).

# 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:**

![](https://assets.leetcode.com/uploads/2019/05/03/1336_ex1.JPG)

```
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:**

![](https://assets.leetcode.com/uploads/2019/05/03/1336_ex2.JPG)

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

```cpp
// 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);
}
```