代码随想录算法训练营第五十一天｜99.岛屿数量 深搜 、99.岛屿数量 广搜、岛屿的最大面积

#99. 岛屿数量

深度优先搜索：

每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

本题思路：用遇到一个没有遍历过的节点陆地，计数器就加一，然后把该节点陆地所能遍历到的陆地都标记上。在遇到标记过的陆地节点和海洋节点的时候直接跳过。 这样计数器就是最终岛屿的数量。

def dfs(grid, visited, x, y):if visited[x][y] or grid[x][y] == 0:return  # 终止条件：访问过的节点 或者 遇到海水visited[x][y] = True  # 标记访问过directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]  # 四个方向（上右下左的顺序）for dx, dy in directions:nextx = x + dxnexty = y + dyif 0 <= nextx < len(grid) and 0 <= nexty < len(grid[0]):  # 检查是否越界dfs(grid, visited, nextx, nexty)def main():n, m = map(int, input().split())grid = [list(map(int, input().split())) for _ in range(n)]visited = [[False] * m for _ in range(n)]result = 0for i in range(n):for j in range(m):if not visited[i][j] and grid[i][j] == 1:result += 1  # 遇到没访问过的陆地，+1dfs(grid, visited, i, j)  # 将与其链接的陆地都标记上 Trueprint(result)if __name__ == "__main__":main()

广度优先搜索：

from collections import dequedef bfs(grid, visited, x, y):# 使用deque实现队列queue = deque([(x, y)])visited[x][y] = True  # 加入队列后立即标记为已访问directions = [[0,1],[1,0],[0,-1],[-1,0]]while queue:curx, cury = queue.popleft()  # 从队列中取出当前位置for dx, dy in directions:  # 遍历四个方向nextx, nexty = curx + dx, cury + dy# 检查新位置是否在网格内if 0 <= nextx < len(grid) and 0 <= nexty < len(grid[0]):# 如果新位置未被访问且是陆地，则加入队列并标记为已访问if not visited[nextx][nexty] and grid[nextx][nexty] == 1:queue.append((nextx, nexty))visited[nextx][nexty] = Truedef main():n, m = map(int, input().split())# 使用列表推导式初始化网格和访问记录grid = [list(map(int, input().split())) for _ in range(n)]visited = [[False] * m for _ in range(n)]result = 0# 遍历网格，找到未访问的陆地，计算陆地区域数量for i in range(n):for j in range(m):if not visited[i][j] and grid[i][j] == 1:result += 1bfs(grid, visited, i, j)print(result)if __name__ == "__main__":main()

100. 岛屿的最大面积

DFS写法：

dfs只处理下一个节点，即在主函数遇到岛屿就计数为1，dfs处理接下来的相邻陆地

def dfs(grid, visited, x, y):# 定义四个方向directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]if visited[x][y] or grid[x][y] == 0:  # 终止条件：访问过的节点 或者 遇到海水returnvisited[x][y] = True  # 标记访问过global count  # 使用全局变量count，因为需要在dfs调用之间共享状态count += 1for dx, dy in directions:nextx = x + dxnexty = y + dy# 检查新坐标是否越界if 0 <= nextx < len(grid) and 0 <= nexty < len(grid[0]):dfs(grid, visited, nextx, nexty)  # 递归调用dfsdef find_max_island_area(grid):# 获取网格的行数和列数n = len(grid)m = len(grid[0])# 初始化访问记录矩阵visited = [[False] * m for _ in range(n)]# 初始化结果变量result = 0for i in range(n):  # 遍历网格for j in range(m):if not visited[i][j] and grid[i][j] == 1:  # 如果是未访问的陆地count = 0  # 重置计数器dfs(grid, visited, i, j)  # 执行深度优先搜索result = max(result, count)  # 更新最大陆地区域大小return result

BFS写法：

from collections import dequeclass Solution:def maxAreaOfIsland(self, grid):# 定义四个方向self.dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]# 初始化结果变量result = 0# 遍历网格，寻找未访问的陆地for i in range(len(grid)):for j in range(len(grid[0])):if grid[i][j] == 1:# 使用bfs算法计算陆地区域大小area = self.bfs(grid, i, j)result = max(result, area)return resultdef bfs(self, grid, x, y):# 检查坐标是否越界if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]):return 0# 访问记录集合visited = [[False] * len(grid[0]) for _ in range(len(grid))]# 初始化队列queue = deque([(x, y)])# 初始化陆地区域计数count = 1while queue:# 从队列中取出当前坐标xx, yy = queue.popleft()# 标记当前坐标为已访问visited[xx][yy] = True# 遍历四个方向for dx, dy in self.dir:nextx, nexty = xx + dx, yy + dy# 如果新坐标在网格内且未被访问过且是陆地if 0 <= nextx < len(grid) and 0 <= nexty < len(grid[0]) and not visited[nextx][nexty] and grid[nextx][nexty] == 1:# 将新坐标加入队列queue.append((nextx, nexty))# 标记新坐标为已访问visited[nextx][nexty] = True# 更新陆地区域计数count += 1return count# 示例使用
# 假设有一个网格
grid = [[1, 1, 0, 0, 0],[1, 1, 0, 0, 0],[0, 0, 0, 1, 1],[0, 0, 0, 1, 1]
]
# 创建Solution实例并调用maxAreaOfIsland方法
solution = Solution()
print(solution.maxAreaOfIsland(grid))