1 算法模板
void dfs(int[][] grid, int r, int c) {
// 判断 base case
// 如果坐标 (r, c) 超出了网格范围,直接返回
if (!inArea(grid, r, c)) {
return;
}
// 访问上、下、左、右四个相邻结点
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判断坐标 (r, c) 是否在网格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
2 代码
class Solution:
def dfs(self, grid, i, j):
# 边界处理
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
return
# base case
if grid[i][j] == "0":
return
if grid[i][j] == "1":
grid[i][j] = "-1"
self.dfs(grid, i, j - 1)
self.dfs(grid, i, j + 1)
self.dfs(grid, i + 1, j)
self.dfs(grid, i - 1, j)
def numIslands(self, grid: List[List[str]]) -> int:
cnt = 0
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == "1":
self.dfs(grid, i, j)
cnt += 1
return cnt
标签:return,int,self,dfs,----,grid,DFS,len,LeetCode
From: https://www.cnblogs.com/liuyechang/p/17467121.html