图论算法之深度遍历岛屿问题

200. 岛屿数量 - 力扣LeetCodeclass Solution { public int numIslands(char[][] grid) { int res 0; for(int r 0; r grid.length; r){ for(int c 0; cgrid[0].length; c){ if(grid[r][c] 1){ res; dfs(grid, r,c); } } } return res; } //从岛屿位置rc出发遍历完这个岛屿 void dfs(char [][] grid, int r, int c){ if(!inArea(grid, r, c)){ return; } if(grid[r][c]!1){ return; } grid[r][c] 2; dfs(grid, r-1, c); dfs(grid, r1, c); dfs(grid, r, c-1); dfs(grid, r, c1); } boolean inArea(char [][]grid, int r, int c){ return r 0 c 0 r grid.length c grid[0].length; } }695. 岛屿的最大面积 - 力扣LeetCodeclass Solution { public int maxAreaOfIsland(int[][] grid) { int res 0; for(int r 0; r grid.length; r){ for(int c 0; cgrid[0].length; c){ if(grid[r][c] 1){ res Math.max(res,dfs(grid, r,c)); } } } return res; } //从岛屿位置rc出发遍历完这个岛屿的面积 int dfs(int [][] grid, int r, int c){ if(!inArea(grid, r, c)){ return 0; } if(grid[r][c]!1){ return 0; } grid[r][c] 2; return 1 dfs(grid, r-1, c) dfs(grid, r1, c) dfs(grid, r, c-1) dfs(grid, r, c1); } boolean inArea(int [][]grid, int r, int c){ return r 0 c 0 r grid.length c grid[0].length; } }两题都是深度优先遍历模版为先遍历每个为1的数据然后递归进去按四个方向查找递归里判断越界和已访问数据给已访问数据改为2注意dfs的方法含义。