代码随想录|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.问题
总结
输入输出