LeetCodeCampsDay52图论part03

101.孤岛的总面积

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要计算所有孤岛的总面积，岛屿面积的计算方式为组成岛屿的陆地的总数。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0。

输出描述

输出一个整数，表示所有孤岛的总面积，如果不存在孤岛，则输出 0。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

1

提示信息

在矩阵中心部分的岛屿，因为没有任何一个单元格接触到矩阵边缘，所以该岛屿属于孤岛，总面积为 1。

数据范围：

1 <= M, N <= 50。

思路0

题目要求没有任何一个单元格接触到矩阵边缘，那：从四个边缘出发，将与之相邻的格子都变成海洋（设置为0），随后再统计保留下来为陆地的格子即可

如图，在遍历地图周围四个边，靠地图四边的陆地，都为绿色，

在遇到地图周边陆地的时候，将1都变为0，此时地图为这样：

然后我们再去遍历这个地图，遇到有陆地的地方，去采用深搜或者广搜，边统计所有陆地。

代码0

direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]
# 
from collections import deque

# 将x,y相邻的位置都变成海洋（0)
def bfs(graph, x, y):
    que = deque()
    que.append([x, y])

    while que:
        curX, curY = que.popleft()
        graph[curX][curY] = 0
        for i, j in direction:
            nextX = curX + i
            nextY = curY + j
            if nextX < 0 or nextY < 0 or nextX >= len(graph) or nextY >= len(graph[0]):
                continue

            if graph[nextX][nextY] == 1:
                que.append([nextX, nextY])


def main():
    n, m = map(int, input().split())
    graph = list()
    for _ in range(n):
        graph.append(list(map(int, input().split())))
    
    res = 0
    
    # 从上、下开始将相邻格子变成海洋
    for i in range(m):
        if graph[0][i] == 1:
            bfs(graph, 0, i)
        if graph[n - 1][i] == 1:
            bfs(graph, n - 1, i)
    
    # 从左、右开始将相邻格子变成海洋
    for i in range(n):
        if graph[i][0] == 1:
            bfs(graph, i, 0)
        if graph[i][m - 1] == 1:
            bfs(graph, i, m - 1)


    for i in range(1, n - 1):
        for j in range(1, m - 1):
            if graph[i][j] == 1:
                res += 1

    print(res)

if __name__ == "__main__":
    main()

广度优先搜索思路一

我的思路是，对每个格子遍历，如果这个格子搜索到的相邻格子是边缘位置，则将它标记，并最终将整个区域返回-1；否则就返回实际的面积值；实际取所有返回值的最大值

广度优先搜索思路二

• 时间复杂度O(M * N)
• 空间复杂度O(M * N)

# 如果某个岛在边缘上则直接返回-1
# 否则才计算这个岛的面积

direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]

def bfs(graph, visited, x, y) -> int:
    # 
    from collections import deque

    que = deque()
    que.append([x, y])

    area = 1
    flag = 0
    while que:
        curX, curY = que.popleft()
        for i, j in direction:
            nextX = curX + i
            nextY = curY + j
            if nextX < 0 or nextY < 0 or nextX >= len(graph) or nextY >= len(graph[0]):
                continue

            if graph[nextX][nextY] == 1 and visited[nextX][nextY] == 2:
                flag = 1

            if graph[nextX][nextY] == 1 and visited[nextX][nextY] == 0:
                if nextX == 0 or nextY == 0 or nextX == len(graph) - 1 or nextY == len(graph[0]) - 1:
                    visited[nextX][nextY] = 2
                    flag = 1
                else:
                    visited[nextX][nextY] = 1
                    area += 1
                que.append([nextX, nextY])
    if flag == 1:
        return -1
    return area

def main():
    n, m = map(int, input().split())
    graph = list()
    for _ in range(n):
        graph.append(list(map(int, input().split())))
    
    res = 0
    visited = [[0] * m for _ in range(n)]
    for i in range(1, n - 1):
        for j in range(1, m - 1):
            if visited[i][j] == 0 and graph[i][j] == 1:
                visited[i][j] = 1
                res += max(bfs(graph, visited, i, j), 0)

    print(res)

if __name__ == "__main__":
    main()

102.沉没孤岛

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域，且完全被水域单元格包围。孤岛是那些位于矩阵内部、所有单元格都不接触边缘的岛屿。

现在你需要将所有孤岛“沉没”，即将孤岛中的所有陆地单元格（1）转变为水域单元格（0）。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。

之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出将孤岛“沉没”之后的岛屿矩阵。 注意：每个元素后面都有一个空格

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

1 1 0 0 0
1 1 0 0 0
0 0 0 0 0
0 0 0 1 1

提示信息

将孤岛沉没。

数据范围：

1 <= M, N <= 50。

# 从上、下、左、右开始将与边缘格子相邻的格子保持为陆地
# 将孤岛变成海洋

direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]

def bfs(graph, x, y):
    from collections import deque
    que = deque()
    que.append([x, y])

    while que:
        curx, cury = que.popleft()
        # 设置为2表示可以被保留
        graph[curx][cury] = -1
        for i, j in direction:
            nextx = curx + i
            nexty = cury + j
            if nextx < 0 or nexty < 0 or nextx >= len(graph) or nexty >= len(graph[0]):
                continue
            
            if graph[nextx][nexty] == 1:
                que.append([nextx, nexty])
            

def main():
    n, m = map(int, input().split())
    graph = list()
    for i in range(n):
        graph.append(list(map(int, input().split())))
    
    # 从上、下两行开始
    for i in range(m):
        if graph[0][i] == 1:
            bfs(graph, 0, i)
        if graph[n - 1][i] == 1:
            bfs(graph, n - 1, i)
    
    # 从左、右两列开始
    for i in range(n):
        if graph[i][0] == 1:
            bfs(graph, i, 0)
        if graph[i][m - 1] == 1:
            bfs(graph, i, m - 1)
    
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 1:
                graph[i][j] = 0
            if graph[i][j] == -1:
                graph[i][j] = 1
    
    for line in graph:
        for i in line:
            print(i, end=" ")
        print("")
    
if __name__ == "__main__":
    main()

103 水流问题

https://kamacoder.com/problempage.php?pid=1175

题目描述

现有一个 N × M 的矩阵，每个单元格包含一个数值，这个数值代表该位置的相对高度。矩阵的左边界和上边界被认为是第一组边界，而矩阵的右边界和下边界被视为第二组边界。

矩阵模拟了一个地形，当雨水落在上面时，水会根据地形的倾斜向低处流动，但只能从较高或等高的地点流向较低或等高并且相邻（上下左右方向）的地点。我们的目标是确定那些单元格，从这些单元格出发的水可以达到第一组边界和第二组边界。

输入描述

第一行包含两个整数 N 和 M，分别表示矩阵的行数和列数。

后续 N 行，每行包含 M 个整数，表示矩阵中的每个单元格的高度。

输出描述

输出共有多行，每行输出两个整数，用一个空格隔开，表示可达第一组边界和第二组边界的单元格的坐标，输出顺序任意。

输入示例

5 5
1 3 1 2 4
1 2 1 3 2
2 4 7 2 1
4 5 6 1 1
1 4 1 2 1

输出示例

0 4
1 3
2 2
3 0
3 1
3 2
4 0
4 1

提示信息

图中的蓝色方块上的雨水既能流向第一组边界，也能流向第二组边界。所以最终答案为所有蓝色方块的坐标。

数据范围：

1 <= M, N <= 100。

搜索思路

一个比较直白的想法，其实就是 遍历每个点，然后看这个点 能不能同时到达第一组边界和第二组边界。

至于遍历方式，可以用dfs，也可以用bfs，以下用dfs来举例。

这种思路很直白，但很明显，以上代码超时了。 来看看时间复杂度。

遍历每一个节点，是 m * n，遍历每一个节点的时候，都要做深搜，深搜的时间复杂度是： m * n

那么整体时间复杂度 就是 O(m^2 * n^2) ，这是一个四次方的时间复杂度。

那么我们可以 反过来想，从第一组边界上的节点 逆流而上，将遍历过的节点都标记上。

同样从第二组边界的边上节点 逆流而上，将遍历过的节点也标记上。

然后两方都标记过的节点就是既可以流向第一组边界也可以流向第二组边界的节点。

从第一组边界边上节点出发，如图： （图中并没有把所有遍历的方向都画出来，只画关键部分）

从第二组边界上节点出发，如图： （图中并没有把所有遍历的方向都画出来，只画关键部分）

最后，我们得到两个方向交界的这些节点，就是我们最后要求的节点。

深度优先搜索代码

那么本题整体的时间复杂度其实是： 2 * n * m + n * m ，所以最终时间复杂度为 O(n * m) 。

空间复杂度为：O(n * m) 这个就不难理解了。开了几个 n * m 的数组

firstborder = set()
secondborder = set()
direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]

def dfs(graph, visited, border, x, y):
    if visited[x][y] == 1:
        return
    
    visited[x][y] = 1
    border.add((x, y))

    for i, j in direction:
        nextx = x + i
        nexty = y + j

        if 0 <= nextx < len(graph) and 0 <= nexty < len(graph[0]) and int(graph[x][y]) <= int(graph[nextx][nexty]):
            dfs(graph, visited, border, nextx, nexty)


def main():
    global firstborder, secondborder

    n, m = map(int, input().split())

    graph = list()
    for _ in range(n):
        graph.append(list(map(int, input().split())))
    
    visited = [[0] * m for _ in range(n)]
    for i in range(n):
        # 从第一边界（第一列）和从第一边界（第一行）出发
        dfs(graph, visited, firstborder, i, 0)
    for i in range(m):
        dfs(graph, visited, firstborder, 0, i)
        
    
    visited = [[0] * m for _ in range(n)]
    for i in range(n):
        # 第二边界（最后一列）和第二边界（最后一行）出发
        dfs(graph, visited, secondborder, i, m - 1)
    for i in range(m):
        dfs(graph, visited, secondborder, n - 1, i)

        
    res = firstborder & secondborder
    # 最后统计同时出现在firstborder和secondborder里的

    for x, y in res:
        print(f"{x} {y}")

if __name__ == "__main__":
    main()

广度优先思路

只有写法和深度优先不太一样，注意将visited的判断放在while循环内

广度优先代码

那么本题整体的时间复杂度其实是： 2 * n * m + n * m ，所以最终时间复杂度为 O(n * m) 。

空间复杂度为：O(n * m) 这个就不难理解了。开了几个 n * m 的数组

def bfs(graph, visited, border, x, y):
    from collections import deque
    que = deque()
    que.append([x, y])

    while que:
        curx, cury = que.popleft()
        if visited[curx][cury] == 1:
            continue
        
        visited[curx][cury] = 1
        border.add((curx, cury))

        for i, j in direction:
            nextx = curx + i
            nexty = cury + j
            if 0 <= nextx < len(graph) and 0 <= nexty < len(graph[0]) and int(graph[curx][cury]) <= int(graph[nextx][nexty]):
                que.append([nextx, nexty])

                
def main():
    global firstborder, secondborder

    n, m = map(int, input().split())

    graph = list()
    for _ in range(n):
        graph.append(list(map(int, input().split())))
    
    visited = [[0] * m for _ in range(n)]
    for i in range(n):
        # 从第一边界（第一列）和从第一边界（第一行）出发
        bfs(graph, visited, firstborder, i, 0)
    for i in range(m):
        bfs(graph, visited, firstborder, 0, i)
        
    
    visited = [[0] * m for _ in range(n)]
    for i in range(n):
        # 第二边界（最后一列）和第二边界（最后一行）出发
        bfs(graph, visited, secondborder, i, m - 1)
    for i in range(m):
        bfs(graph, visited, secondborder, n - 1, i)

        
    res = firstborder & secondborder
    # 最后统计同时出现在firstborder和secondborder里的

    for x, y in res:
        print(f"{x} {y}")

if __name__ == "__main__":
    main()

104.建造最大岛屿

https://kamacoder.com/problempage.php?pid=1176

题目描述

给定一个由 1（陆地）和 0（水）组成的矩阵，你最多可以将矩阵中的一格水变为一块陆地，在执行了此操作之后，矩阵中最大的岛屿面积是多少。

岛屿面积的计算方式为组成岛屿的陆地的总数。岛屿是被水包围，并且通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设矩阵外均被水包围。

输入描述

第一行包含两个整数 N, M，表示矩阵的行数和列数。之后 N 行，每行包含 M 个数字，数字为 1 或者 0，表示岛屿的单元格。

输出描述

输出一个整数，表示最大的岛屿面积。

输入示例

4 5
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

输出示例

6

提示信息

对于上面的案例，有两个位置可将 0 变成 1，使得岛屿的面积最大，即 6。

数据范围：

1 <= M, N <= 50。

搜索代码

其实每次深搜遍历计算最大岛屿面积，我们都做了很多重复的工作。

只要用一次深搜把每个岛屿的面积记录下来就好。

第一步：一次遍历地图，得出各个岛屿的面积，并做编号记录。可以使用map记录，key为岛屿编号，value为岛屿面积

第二步：再遍历地图，遍历0的方格（因为要将0变成1），并统计该1（由0变成的1）周边岛屿面积，将其相邻面积相加在一起，遍历所有 0 之后，就可以得出 选一个0变成1 之后的最大面积。

拿如下地图的岛屿情况来举例： （1为陆地）

第一步，则遍历地图，并将岛屿的编号和面积都统计好，过程如图所示：

这个过程时间复杂度 n * n 。可能有录友想：分明是两个for循环下面套这一个dfs，时间复杂度怎么回事 n * n呢？

其实大家可以仔细看一下代码，n * n这个方格地图中，每个节点我们就遍历一次，并不会重复遍历。

第二步过程如图所示：

也就是遍历每一个0的方格，并统计其相邻岛屿面积，最后取一个最大值。

这个过程的时间复杂度也为 n * n。

所以整个解法的时间复杂度，为 n * n + n * n 也就是 n^2。

当然这里还有一个优化的点，就是 可以不用 visited数组，因为有mark来标记，所以遍历过的grid[i][j]是不等于1的。

广度优先代码

# 技巧解题
# 先把所有岛屿面积求出来，并且给这个岛屿进行编号（需要修改graph里这个岛屿块数值），并记录这个编号岛屿的面积（放在字典里）
# 再遍历所有海洋（假设把当前海洋变成陆地），并且计算当前这块海洋相邻的岛屿总面积，就能找到一个最合适变成陆地的海洋块

direction = [[0, 1], [1, 0], [-1, 0], [0, -1]]

# bfs的目的是计算每个岛屿的面积，以及将岛屿“涂色”，同一个岛屿将拥有相同的编号
def bfs(graph, visited, x, y, number) -> int:
    
    from collections import deque

    area = 1
    que = deque()
    que.append([x, y])

    while que:
        curx, cury = que.popleft()
        # 进行岛屿编号
        graph[curx][cury] = number
        
        for i, j in direction:
            nextx = curx + i
            nexty = cury + j
            if 0<= nextx < len(graph) and 0<= nexty < len(graph[0]) and visited[nextx][nexty] == 0 and graph[nextx][nexty] == 1:
              	# 注意计算面积的位置
                visited[nextx][nexty] = 1
                area += 1
                
                que.append([nextx, nexty])
    
    return area



def main():
    n, m = map(int, input().split())

    graph = list()

    for _ in range(n):
        graph.append(list(map(int, input().split())))
    
    number = 1
    # res为最大岛屿面积
    res = 0
    table = dict()
    visited = [[0] * (m) for _ in range(n)]
    # 第一次遍历，将岛屿编号并且记录最大面积
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0 and visited[i][j] == 0:
                number += 1
                temp  = bfs(graph, visited, i, j, number)
                res = max(res, temp)
                table[number] = temp
    
    # 第二次遍历，只针对海洋进行操作
    # 对海洋块的周围岛屿进行计算，注意某一个海洋块，有可能被同一个编号的岛屿包围，所以不要重复添加某个岛屿
    for x in range(n):
        for y in range(m):
            # 如果为海洋
            if graph[x][y] == 0:
                temp = 1
                # 记录是否已经添加过某个岛屿
                added = set()
                for i, j in direction:
                    nextx = x + i
                    nexty = y + j
                    if 0<= nextx < len(graph) and 0<= nexty < len(graph[0]) and graph[nextx][nexty] != 0:
                        if graph[nextx][nexty] not in added:
                            temp += table[graph[nextx][nexty]]
                            added.add(graph[nextx][nexty])
                # 求岛屿最大面积
                res = max(temp, res)

    print(res)

if __name__ == "__main__":
    main()