1162. 地图分析#

1
你现在手里有一份大小为 N x N 的 网格 grid，
2

3
上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，
4

5
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。
6

7
我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：
8

9
(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。
10

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

13

14

15
示例 1：
16

17

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

24

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

30

31
提示：
32

33
1 <= grid.length == grid[0].length <= 100
34
grid[i][j] 不是 0 就是 1

1
class Solution {
2
private:
3
    vector<vector<int>> dis = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
4
public:
5
    int maxDistance(vector<vector<int>>& grid) {
6
        int m = grid.size(), n = grid[0].size();
7
        deque<pair<int, int>> q;
8
        for(int i = 0; i < m; i++)
9
        {
10
            for(int j = 0; j < n; j++)
11
            {
12
                if(grid[i][j] == 1)
13
                {
14
                    q.push_back({i, j});
15
                }
16
            }
17
        }
18
        //无陆地或者海洋则返回；
19
        if(q.size() == 0 || q.size() == m * n) return -1;
20

21
        int ans = -1;
22
        while(!q.empty())
23
        {
24
            ans++;
25
            int s = q.size();
26
            while(s--)
27
            {
28
                auto k = q.front(); q.pop_front();
29
                for(auto& d : dis)
30
                {
31
                   int x = k.first + d[0];
32
                   int y = k.second + d[1];
33
                    // 如果搜索到的新坐标超出范围/陆地/已经遍历过，则不搜索了
34
                    if(x < 0 || x >= m || y < 0 || y >= n || grid[x][y] != 0) continue;
35
                    //搜索后记为-1，表示不能再遇见
36
                    grid[x][y] = -1;
37
                    q.push_back({x, y});
38
                }
39
            }
40
        }
41
        return ans;
42
    }
43
};