在做岛屿类问题的时候请先看作者：nettee的题解，讲的真的特别好，看了他的题解在自己做题！！！！！
链接：https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/
200. 岛屿数量
image.png
这道题的思路是用dfs遍历连续1的点，同时遍历的时候记得要把遍历过的1变成2，这样子后面才不会重复遍历或者进入绕圈圈的情况。
图的遍历模板就是这个：
void dfs(int[][] grid, int r, int c) {
// 判断 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果这个格子不是岛屿，直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 将格子标记为「已遍历过」
// 访问上、下、左、右四个相邻结点
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;
}
所以完整ac答案如下：
class Solution {
public int numIslands(char[][] grid) {
int row = grid.length;
int col = grid[0].length;
int count = 0;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j]=='1'){
dfs(grid,i,j);
count++;
}
}
}
return count;
}
public void dfs(char[][] grid,int i,int j){
if(!isArea(grid,i,j)){
return ;
}
if(grid[i][j]!='1'){
return;
}
grid[i][j] = '2';
dfs(grid,i-1,j);
dfs(grid,i,j-1);
dfs(grid,i+1,j);
dfs(grid,i,j+1);
}
public boolean isArea(char[][] grid,int i,int j){
return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
}
}
695. 岛屿的最大面积
image.png
解题思路和上面的差不多，就是在dfs的时候记录一下到底有多少个1，然后保留最大值就行
static int ans =0 ;
static int res = 0;
public int maxAreaOfIsland(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j]==1){
dfs(grid,i,j);
ans = Math.max(ans,res);
res = 0;
}
}
}
return ans;
}
public void dfs(int[][] grid,int i,int j){
if(!isArea(grid,i,j)){
return ;
}
if(grid[i][j]!=1){
return;
}
grid[i][j] = 2;
res++;
dfs(grid,i-1,j);
dfs(grid,i,j-1);
dfs(grid,i+1,j);
dfs(grid,i,j+1);
}
public boolean isArea(int[][] grid,int i,int j){
return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
}
463. 岛屿的周长
image.png
这道题用数学的方式做其实比用dfs来的好理解和块，但是既然是训练模板，所以还是尝试用dfs解决，这边动用了一个很巧妙的思想，就是dfs边界的问题，第一种情况是dfs到了一个1，他的其他方向没有1了，这时候返回，相当于多了一个海洋的边界；另一个情况是dfs遍历到了矩阵的四周，返回的话就一个边界的边。
class Solution {
public int islandPerimeter(int[][] grid) {
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
// 题目限制只有一个岛屿，计算一个即可
return dfs(grid, r, c);
}
}
}
return 0;
}
int dfs(int[][] grid, int r, int c) {
// 函数因为「坐标 (r, c) 超出网格范围」返回，对应一条黄色的边
if (!inArea(grid, r, c)) {
return 1;
}
// 函数因为「当前格子是海洋格子」返回，对应一条蓝色的边
if (grid[r][c] == 0) {
return 1;
}
// 函数因为「当前格子是已遍历的陆地格子」返回，和周长没关系
if (grid[r][c] != 1) {
return 0;
}
grid[r][c] = 2;
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;
}
}
