200. 岛屿数量
class Solution {
//利用深度递归解决,可以看图,并加记住这个模板,他可以解决岛屿中的问题,还有一题岛屿面积问题也是这个模板。
public int numIslands(char[][] grid) {
//定义一个表示岛屿数量的变量
int count = 0;
//这个两层for循环是用来遍历整张二维表格中所有的陆地
//其中 i 表示行,j 表示列
for(int i = 0; i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
//取出所有的陆地
if(grid[i][j] == '1'){
//深度递归,遍历所有的陆地
dfs(grid,i,j);
//用来统计有多少岛屿,岛屿是由多个陆地组成的,概念不一样
count++;
}
}
}
//返回岛屿的数量
return count;
}
public void dfs(char[][] grid,int i, int j){
//防止 i 和 j 越界,也就是防止超出岛屿(上下左右)的范围。特别注意当遍历到海洋的时候也退出循环
if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]=='0') return;
//将遍历过的陆地改为海洋,防止重复遍历
grid[i][j]='0';
//上,
dfs(grid,i+1,j);
//下
dfs(grid,i-1,j);
//右
dfs(grid,i,j+1);
//左
dfs(grid,i,j-1);
}
}
695. 岛屿的最大面积
class Solution {
public int maxAreaOfIsland(int[][] grid) {
//定义一个表示最大值变量
int max = 0;
//这个两层for循环是用来遍历整张二维表格中所有的陆地
//其中 i 表示行,j 表示列
for(int i = 0; i<grid.length;i++){
for(int j =0;j<grid[0].length;j++){
//取出所有的陆地
if(grid[i][j] == 1){
//深度递归,遍历所有的陆地,并计算得到岛屿面积的大小
int area = dfs(grid,i,j,0);
// 和最大值进行比较
max = Math.max(area,max);
}
}
}
//返回最大值
return max;
}
public int dfs(int[][] grid,int i, int j,int area){
//防止 i 和 j 越界,也就是防止超出岛屿(上下左右)的范围。特别注意当遍历到海洋的时候也退出循环,返回0
if(i<0||j<0||i>=grid.length||j>=grid[0].length||grid[i][j]==0) return 0;
//将遍历过的陆地改为海洋,防止重复遍历
grid[i][j]= 0;
// 记录最大值(此处+1就是加的当前的值)
return dfs(grid,i+1,j,area)+dfs(grid,i-1,j,area)+dfs(grid,i,j+1,area)+dfs(grid,i,j-1,area)+1;
}
}
转载:https://leetcode.cn/problems/number-of-islands/solutions/211211/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/