# \[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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://kerasnoone.gitbook.io/garnet/suan-fa/bfs/1162-di-tu-fen-xi.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.