DFS

发表于 | 分类于
深度优先遍历算法

直接看题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
200. 岛屿数量

给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1


示例 2：

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

找到一个1后，就顺着这个1的四个方向，去查找是1的点，然后一直查找下去，直到周围都是0，或者碰到边缘了，为了避免原来的1被重新访问，将遍历过的1改为0即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def dfs(i,j,grid):
	# 当当前节点是不在网格中，或者当前的节点是水，那么这次深度便利结束
	if i<0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == "0":
		return
	# 将当前节点设置为已经被访问过
	grid[i][j] ="0"

	# 遍历当前节点的周边节点
	dfs(i,j+1,grid)
	dfs(i+1,j,grid)
	dfs(i,j-1,grid)
	dfs(i-1,j,grid)

def getIslandNum(grid):
	num = 0
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] == "1":
				num += 1
				dfs(i,j,grid)
	return num