图论——求孤岛面积、淹没孤岛（python）

思路1.求孤岛面积孤岛指的是四周都是水的岛屿。遍历边界周围的岛屿将它们全部淹没grid[i][j]0,最后再次扫描网格统计1的个数。#求孤岛面积 # 4 5 # 1 1 1 1 0 # 1 1 0 1 0 # 1 1 0 0 0 # 0 0 0 0 0 # 输出 0 def lonelyIslandArea(grid,m,n): dirs[(0,1),(0,-1),(1,0),(-1,0)] #四个方向 #递归逻辑 def dfs(x,y): if x0 or xm or y0 or yn: #判断是否越界 return if grid[x][y]0: #判断是否为陆地 return grid[x][y]0 #将该陆地沉没 for dx,dy in dirs: dfs(xdx,ydy) #遍历网格 for i in range(m): for j in range(n): if grid[i][j]1 and (i0 or im-1 or j0 or jn-1): dfs(i,j) #对于边缘上的陆地调用dfs置为0 #再次遍历岛屿统计孤岛面积 res0 for i in range(m): for j in range(n): if grid[i][j]1: res1 print(res) return res def main(): m,nmap(int,input().split()) grid[] for i in range(m): linelist(map(int,input().split())) grid.append(line) lonelyIslandArea(grid,m,n) if __name____main__: main()2.淹没孤岛遍历边界上的所有岛递归搜索相连的岛屿全部修改标记为2。最后遍历一遍图将所有2修改为1将所有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 # import sys # sys.setrecursionlimit(1000000) def yanmoIsland(grid,m,n): dirs[(0,1),(0,-1),(1,0),(-1,0)] def dfs(x,y): if x0 or xm or y0 or yn: return if grid[x][y]0 or grid[x][y]2: return grid[x][y]2 for dx,dy in dirs: dfs(xdx,ydy) for i in range(m): for j in range(n): if (i0 or im-1 or j0 or jn-1) and grid[i][j]1: #是边缘陆地才能进入dfs递归 dfs(i,j) for i in range(m): for j in range(n): if grid[i][j]2: grid[i][j]1 elif grid[i][j]1: grid[i][j]0 for i in grid: print( .join(map(str,i))) return grid def main(): m,nmap(int,input().split()) grid[] for i in range(m): linelist(map(int,input().split())) grid.append(line) yanmoIsland(grid,m,n) if __name____main__: main()