岛屿的数量

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-islands

例子

  1. 输入：grid = [
  2.   ["1","1","1","1","0"],
  3.   ["1","1","0","1","0"],
  4.   ["1","1","0","0","0"],
  5.   ["0","0","0","0","0"]
  6. ]
  7. 输出：1

思路

使用深度优先遍历的思想进行遍历 - 找到1开始遍历
将遍历过的陆地进行标记grid[i][j] = ‘2’;
1.边界
m = grid.length; n = grid[0].length;
2.进行遍历数组，找到1就开始dfs

  1. for(int i=0;i<m;i++){
  2.     for(int j = 0;j<n;j++){
  3.         // 找到1并进行dfs
  4.         if(grid[i][j]=='1'){
  5.             dfs(grid,i,j,m,n);
  6.             // dfs的次数就是岛屿的次数
  7.             numIslands++;
  8.         }
  9.     }
  10. }

3.在进行dfs的时候
终止条件：a.超出边界的时候 b.等于0或者2的时候就证明遍历过或者为水
否则四个方向继续遍历

  1. void dfs(char[][] grid,int i,int j,int m,int n){
  2.     if(i<0 || j<0 || i>=m || j>=n) return;
  3.     if(grid[i][j]=='0' || grid[i][j]=='2') return;
  4.     grid[i][j] = '2';
  5.     dfs(grid,i+1,j,m,n);
  6.     dfs(grid,i-1,j,m,n);
  7.     dfs(grid,i,j+1,m,n);
  8.     dfs(grid,i,j-1,m,n);
  9. }

岛屿的最大面积

思路

  1. class Solution {
  2.     public int maxAreaOfIsland(int[][] grid) {
  3.         int m = grid.length;
  4.         int n = grid[0].length;
  5.         int max = 0;
  6.         for(int i = 0;i<m;++i){
  7.             for(int j = 0;j<n;j++){
  8.                 if(grid[i][j]==1){
  9.                     max = Math.max(max,dfs(grid,i,j,m,n));
  10.                 }
  11.             }
  12.         }
  13.         return max;
  14.     }
  16.     int dfs(int[][] grid,int i,int j,int m,int n){
  17.         if(i<0 || i>=m || j<0 || j>=n) return 0;
  18.         if(grid[i][j]!=1) return 0;
  19.         grid[i][j] = 2;
  20.         return 1+dfs(grid,i-1,j,m,n)+dfs(grid,i+1,j,m,n)+dfs(grid,i,j-1,m,n)+dfs(grid,i,j+1,m,n);
  21.     }
  22. }


岛屿的周长

在进行岛屿周长计算的时候其实计算的就是每一个陆地与水或者边界相连的边

  1. class Solution {
  2.     // 周长为每一个和水域相连的边或者边界
  3.     public int islandPerimeter(int[][] grid) {
  4.         int m = grid.length;
  5.         if(m==0) return 0;
  6.         int n = grid[0].length;
  7.         for(int i = 0;i<m;i++){
  8.             for(int j = 0;j<n;j++){
  9.                 if(grid[i][j]==1){
  10.                     // 题目只有一个岛屿所以直接返回
  11.                     return dfs(grid,i,j,m,n);
  12.                 }
  13.             }
  14.         }
  15.         return 0;
  16.     }
  18.     int dfs(int[][] grid,int i,int j,int m,int n){
  19.         // 遇到边界可以+1
  20.         if(i<0 || j<0 || i>=m || j>=n) return 1;
  21.         // 表示遇到水域可以+1
  22.         if(grid[i][j]==0) return 1;
  23.         // 表示遍历过的陆地直接返回
  24.         if(grid[i][j]==2) return 0;
  25.         grid[i][j] = 2;
  26.         return dfs(grid,i-1,j,m,n)+dfs(grid,i+1,j,m,n)+dfs(grid,i,j-1,m,n)+dfs(grid,i,j+1,m,n);
  27.     }
  28. }