题目描述

你现在手里有一份大小为 N x N 的『地图』(网格) grid,上面的每个『区域』(单元格)都用 0 和 1 标记好了。其中 0 代表海洋,1 代表陆地,你知道距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆地区域的距离。
我们这里说的距离是『曼哈顿距离』( Manhattan Distance):(x0, y0) 和 (x1, y1) 这两个区域之间的距离是 |x0 - x1| + |y0 - y1| 。
如果我们的地图上只有陆地或者海洋,请返回 -1。

示例1

输入:[[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释:
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。

示例2

输入:[[1,0,0],[0,0,0],[0,0,0]]
输出:4
解释:
海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大,最大距离为 4。

提示

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

分析

这也是一道队列的题目,恰好和我曾经数据结构实验的迷宫类似
首先,将原本grid[i][j] = 1的(陆地)全部入队。
其次我们从一个陆地出发,寻找从上下左右寻找grid[i][j] = 0的地方,第一次循环(循环的结束标志为上一次加入队列的元素未处理个数),将一部分海洋变成陆地,即grid[i][j] = 1。
之后为cnt++,即走一步距离。
重复上面的动作,知道queue没有元素。此时返回cnt即为所求。

参考代码

class Solution {
public:
const int directions[5] = {0, 1, 0, -1, 0};
int maxDistance(vector<vector<int>>& grid) {
int ret = 0;
int N = grid.size();
queue<pair<int, int>> q;
// 将陆地(值为 1)的点入队
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (grid[i][j] == 1) {
q.push({i, j});
}
}
}

// 全是海洋或全是陆地
if (q.size() == 0 || q.size() == N * N)
return -1;

while (!q.empty()) {
int s = q.size();
int r = 0;
while (s != 0) {
pair<int, int> front = q.front();
q.pop();
// 4 个方向遍历
for (int i = 0; i < 4; i++) {
int nx = front.first + directions[i];
int ny = front.second + directions[i + 1];
if (nx >= N || ny >= N || nx < 0 || ny < 0 || grid[nx][ny] == 1)
continue;
r++;
// 这里没有新开二位数组做记录,而是直接在原数组上做标记
grid[nx][ny] = 1;
q.push({nx, ny});
}
s--;
}
if (r > 0)
ret++;
}
return ret;
}
};

谢谢访问