当前位置: 首页> 游戏> 攻略 > 【代码随想录|11数组p2 99. 岛屿数量】

【代码随想录|11数组p2 99. 岛屿数量】

时间:2025/7/9 7:55:03来源:https://blog.csdn.net/daisyholly/article/details/140516026 浏览次数:0次

代码随想录|11数组p2 99. 岛屿数量

  • 一、99. 岛屿数量
    • 1.深搜
    • 2.广搜
    • 2.输入输出
    • 3.问题
  • 总结


python

一、99. 岛屿数量

99. 岛屿数量
dfs
终止条件:已访问或者是海水
参数:grid,和当前的坐标(四周需要一个个的判断)
主题循环:将当前岛屿标记已访问,然后对四周进行搜索

主要的思想:有一个1,就count加1,并且通过dfs把可以连接到的都标记为0

巧妙的把已访问是海水合并了
因此此时的0,有两个含义:a)可以通过之前的1访问; b)是海水。

也就是说把一片岛屿最后化简到了一块
因此在之后的搜索grid[i][j]==1时,只能搜索到下一片的啦

1.深搜

代码如下(示例):

class Solution:def numIsLands(self,grid):if not grid:return 0count=0for i in range(len(grid)):for j in range(len(grid[i])):if grid[i][j]==1:count+=1self.dfs(grid,i,j)return countdef dfs(self,grid,i,j):if i<0 or i>=len(grid) or j<0 or j>=len(grid[0]) or grid[i][j]==0:returngrid[i][j]=0self.dfs(grid,i+1,j)self.dfs(grid,i-1,j)self.dfs(grid,i,j+1)self.dfs(grid,i,j-1)

用回溯算法
右边的右边的右边…一直搜到碰到海水为止

2.广搜

代码如下(示例):

class Solution:def numIsLands(self,grid):dirs = [lambda x, y: (x + 1, y),lambda x, y: (x, y + 1),lambda x, y: (x - 1, y),lambda x, y: (x, y - 1)]if not grid:return 0count=0for i in range(len(grid)):for j in range(len(grid[i])):if grid[i][j]==1:count+=1# self.dfs(grid,i,j)self.bfs(grid,i,j,dirs)return countdef bfs(self,grid,x,y,dirs):queue=deque()queue.append((x,y))grid[x][y]=0while queue:cur=queue.pop()for dir in dirs:next=dir(cur[0],cur[1])if next[0]<0 or next[0]>=len(grid) or next[1]<0 or next[1]>=len(grid[0]):continueif grid[next[0]][next[1]]==1:queue.append((next[0],next[1]))grid[next[0]][next[1]]=0

用队列,先把第一轮的相关元素都存入队列中,然后在第一轮的元素搜完之后再取出之前存入的第二轮要搜的元素
右、下、左、上的判断(于此同时把右右、右下、右左、右上、左右、左下…中满足有岛屿的元素都存好)

2.输入输出

if __name__=="__main__":n,m=list(map(int,input().split()))grid=[[0]*m for _ in range(n)]for i in range(n):line=list(map(int,input().split()))for j in range(m):grid[i][j]=line[j]solution=Solution()result=solution.numIsLands(grid)print(result)

多行输入还是要用for循环来执行

3.问题

总结

输入输出

关键字:【代码随想录|11数组p2 99. 岛屿数量】

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: