题目描述
给定有一份大小为 N x N 的网格 grid
,上面的每个单元格都用 0
和 1
标记好了。其中 0
代表海洋,1
代表陆地,找到距离陆地区域最远的海洋区域是是哪一个吗?请返回该海洋区域到离它最近的陆地区域的距离。
这里说的距离是『曼哈顿距离』(Manhattan Distance):(x0, y0)
和 (x1, y1)
这两个区域之间的距离是 |x0 - x1| + |y0 - y1|
。
如果我们的地图上只有陆地或者海洋,请返回 -1
。
样例
输入:[[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释:
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。
输入:[[1,0,1],[0,0,0],[1,0,1]]
输出:2
解释:
海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。
提示
1 <= grid.length == grid[0].length <= 100
grid[i][j]
为0
或1
算法
(宽度优先搜索 / BFS) $O(nm)$
- 首先将所有 1 位置放入队列,初始化这些位置的距离为 0,其余位置为正无穷。
- 开始宽度优先搜索,每次可以扩展周围的 4 个方向。
- 最后找 0 位置的最大距离。
时间复杂度
- 每个位置最多遍历一次,故时间复杂度为 $O(nm)$。
空间复杂度
- 需要队列和距离数组记录每个点的最短距离,故空间复杂度为 $O(nm)$。
C++ 代码
class Solution {
public:
int maxDistance(vector<vector<int>>& grid) {
const int dx[4] = {0, 1, 0, -1};
const int dy[4] = {1, 0, -1, 0};
int n = grid.size(), m = grid[0].size();
queue<pair<int, int>> q;
vector<vector<int>> dis(n, vector(m, INT_MAX));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grid[i][j] == 1) {
q.push(make_pair(i, j));
dis[i][j] = 0;
}
while (!q.empty()) {
auto u = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
int x = u.first + dx[i], y = u.second + dy[i];
if (x < 0 || x >= n || y < 0 || y >= m)
continue;
if (dis[x][y] > dis[u.first][u.second] + 1) {
dis[x][y] = dis[u.first][u.second] + 1;
q.push(make_pair(x, y));
}
}
}
int ans = -1;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
if (grid[i][j] == 0 && dis[i][j] < INT_MAX)
ans = max(ans, dis[i][j]);
return ans;
}
};