算法工程师第四十四天（99. 岛屿数量 深搜 99. 岛屿数量 广搜 100.岛屿的最大面积 ）

本文主要是介绍算法工程师第四十四天（99. 岛屿数量 深搜 99. 岛屿数量 广搜 100.岛屿的最大面积 ），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考文献 代码随想录

一、岛屿数量

题目描述

给定一个由 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

输出示例

3

提示信息

根据测试案例中所展示，岛屿数量共有 3 个，所以输出 3。

数据范围：

1 <= N, M <= 50

思路分析：遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。再遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。那么如果把节点陆地所能遍历到的陆地都标记上呢，就可以使用 DFS，BFS或者并查集。

深搜版本：

n, m = map(int, input().split())
grid = []
for i in range(n):grid.append(list(map(int, input().split())))visited = [[False] * m for _ in range(n)]  # 标记哪些已经走过的
direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # 四个方向：上、右、下、左  def dfs(x, y):for i, j in direction:  # 从开始的这个点往周围搜x_nex = x +  iy_nex=  y + jif x_nex < 0 or x_nex >= len(grid) or y_nex < 0 or y_nex >= len(grid[0]):  # 一旦x，或者说是y发现超出范围，则不需要往下走，continueif not visited[x_nex][y_nex] and grid[x_nex][y_nex] == 1:  # 如果当前的路并没有走过，那么就从当前点出发，并对对应的标记为truevisited[x_nex][y_nex] = Truedfs(x_nex, y_nex)
res = 0
for i in range(n):for j in range(m):if grid[i][j] == 1 and not visited[i][j]:  # 如果为陆地，并且没有被访问过，那么就要调用深搜模版去寻当前节点周围的陆地res += 1  # 一旦发现新的路段，那么结果就要加1visited[i][j] = True  同时把当前的坐标开始搜索并标记为已经走过dfs(i, j)
print(res)

广搜：

n, m = map(int, input().split())
grid = []
for i in range(n):grid.append(list(map(int, input().split())))visited = [[False] * m for _ in range(n)]
direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # 四个方向：上、右、下、左def bfs(x, y):from collections import dequequeen = deque()queen.append([x, y])visited[x][y] = Truewhile queen:cur_x, cur_y = queen.popleft() for i, j in direction:x_nex = cur_x +  iy_nex=  cur_y + jif x_nex < 0 or x_nex >= len(grid) or y_nex < 0 or y_nex >= len(grid[0]):continueif not visited[x_nex][y_nex] and grid[x_nex][y_nex] == 1:queen.append([x_nex, y_nex])visited[x_nex][y_nex] = Trueres = 0
for i in range(n):for j in range(m):if grid[i][j] == 1 and not visited[i][j]:res += 1bfs(i, j)
print(res)

二、岛屿的最大面积

题目描述

给定一个由 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

输出示例

4

提示信息

样例输入中，岛屿的最大面积为 4。

数据范围：

1 <= M, N <= 50。

深搜：

n, m = map(int, input().split())
grid = []
for i in range(n):grid.append(list(map(int, input().split())))visited = [[False] * m for _ in range(n)]
directions = [[0,-1], [0, 1],[-1,0],[1,0]]  # 每个点的方向
res = 0
count = 0
def dfs(x, y):global count # 定义全句变量for i, j in directions:  # 从当前点遍历到走位的陆地nex_x = x + i  nex_y = y + jif nex_y < 0 or nex_x < 0 or nex_x >= len(grid) or nex_y >= len(grid[0]):continue  # 越界了if grid[nex_x][nex_y] == 1 and not visited[nex_x][nex_y]:  # 当前是陆地并且没有被方访问过visited[nex_x][nex_y] = Truecount += 1dfs(nex_x, nex_y)
for i in range(n):for j in range(m):if not visited[i][j] and grid[i][j] == 1:visited[i][j] = True  # count = 1dfs(i, j)res = max(res, count)print(res)

广搜：

n, m = map(int, input().split())
grid = []
for i in range(n):grid.append(list(map(int, input().split())))visited = [[False] * m for _ in range(n)]
directions = [[0,-1], [0, 1],[-1,0],[1,0]]  # 每个点的方向
res = 0
count = 0
def bfs(x, y):from  collections import dequequeen = deque()queen.append([x, y])global count # 定义全句变量while queen:cur_x, cur_y = queen.popleft()for i, j in directions:  # 从当前点遍历到走位的陆地nex_x = cur_x + i  nex_y = cur_y + jif nex_y < 0 or nex_x < 0 or nex_x >= len(grid) or nex_y >= len(grid[0]):continue  # 越界了if grid[nex_x][nex_y] == 1 and not visited[nex_x][nex_y]:  # 当前是陆地并且没有被方访问过visited[nex_x][nex_y] = Truecount += 1queen.append([nex_x, nex_y])
for i in range(n):for j in range(m):if not visited[i][j] and grid[i][j] == 1:visited[i][j] = True  # count = 1bfs(i, j)res = max(res, count)print(res)

这篇关于算法工程师第四十四天（99. 岛屿数量 深搜 99. 岛屿数量 广搜 100.岛屿的最大面积 ）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---