> For the complete documentation index, see [llms.txt](https://kerasnoone.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://kerasnoone.gitbook.io/garnet/suan-fa/bfs/1162-di-tu-fen-xi.md).

# \[1162]\[中等]\[BFS] 地图分析

## 题目描述

[1162. 地图分析](https://leetcode-cn.com/problems/as-far-from-land-as-possible/)

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

如果网格上只有陆地或者海洋，请返回 -1。

示例 1：

![](/files/-MWJ8nuOpfh0WSGMWCe-)

```
输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。
```

示例 2：

![](/files/-MWJ8nuQ0T49DxTZUooc)

```
输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释： 
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。
```

提示：

* 1 <= grid.length == grid\[0].length <= 100
* grid\[i]\[j] 不是 0 就是 1

## 解题思路

[吃鲸🐳！广搜还能多源？看完秒懂!](https://leetcode-cn.com/problems/as-far-from-land-as-possible/solution/zhen-liang-yan-sou-huan-neng-duo-yuan-kan-wan-miao/)

```python
class Solution:
    def maxDistance(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        seen = [[False] * m for _ in range(n)]
        directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        level = 0
        queue = []
        count = 0
        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    queue.append((i, j))
                    seen[i][j] = True
                    count += 1
        if count == 0 or count == n * m:
            return -1

        while queue:
            num_level = len(queue)
            for _ in range(num_level):
                i, j = queue.pop(0)
                for di, dj in directions:
                    ii, jj = i + di, j + dj
                    if 0 <= ii < n and 0 <= jj < m and seen[ii][jj] is False:
                        queue.append((ii, jj))
                        seen[ii][jj] = True
            level += 1

        return level - 1
```