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

---

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.问题

总结

输入输出