LeetCode 1162. 地图分析

发表于 | 分类于 | 评论数： | 阅读次数：

你现在手里有一份大小为 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
39
int 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)。