你现在手里有一份大小为 N x N 的地图(网格)grid
,上面的每个区域(单元格)都用 0
和 1
标记好了。其中 0
代表海洋,1
代表陆地,请你找出一个海洋区域,这个海洋区域到离它最近的陆地区域的距离是最大的。
我们这里说的距离是「曼哈顿距离」:(x0, y0)
和 (x1, y1)
这两个区域之间的距离是 |x0 - x1| + |y0 - y1|
。
如果我们的地图上只有陆地或者海洋,请返回 -1
。
示例 1:1
2
3
4
5
6输入:
[[1,0,1],
[0,0,0],
[1,0,1]]
输出:2
解释:海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。
示例 2:1
2
3
4
5
6输入:
[[1,0,0],
[0,0,0],
[0,0,0]]
输出:4
解释:海洋区域 (2, 2) 和所有陆地区域之间的距离都达到最大,最大距离为 4。
题解:
多源BFS。先把所有 1
(陆地)入队,每次循环把队首上下左右四个方向的海洋入队。为了防止重复搜索,把搜到的海洋标记为 1
。最后一个出队的一定是离陆地最远的。
代码:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39int maxDistance(int **grid, int gridSize, int *gridColSize)
{
int queue[10000][3];
int front = 0, rear = 0;
int i, j, x, y;
int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
for(i = 0; i < gridSize; ++i)
for(j = 0; j < gridSize; ++j)
if(grid[i][j])
{
queue[rear][0] = i;
queue[rear][1] = j;
queue[rear][2] = 0;
rear++;
}
if(!rear || rear == gridSize*gridSize)
return -1;
while(rear > front)
{
for(i = 0; i < 4; ++i)
{
x = queue[front][0] + direction[i][0];
y = queue[front][1] + direction[i][1];
if(x >= 0 && x < gridSize && y >= 0 && y < gridSize && !grid[x][y])
{
grid[x][y] = 1;
queue[rear][0] = x;
queue[rear][1] = y;
queue[rear][2] = queue[front][2]+1;
rear++;
}
}
front++;
}
return queue[front-1][2];
}
这种解法的时间复杂度和空间复杂度显然都是 O(n2)。