图论part2｜200. 岛屿数量、695. 岛屿的最大面积

200、岛屿数量

• 🔗：200. 岛屿数量 - 力扣（LeetCode）
• 思路：
  • 1. 深度优先算法
    • 二叉树中dfs要素：1、访问左右相邻子节点 2、判断base case（终止条件）
    • 参考二叉树中的dfs看网格问题
    • 1. 网格的相邻节点：上下左右4个
    • 2.终止条件：超出格子的范围（--对应二叉树中全部为null的base case）
    • 3. 关键！！避免重复遍历，做过的格子需要进行标记
  • 2. 广度优先算法
    • 扫描整个二维网格，遇到为1的格子，加入队列当中，进行广度搜索
• 代码
  • 深度优先算法

  • class Solution {
    
        public int numIslands(char[][] grid) {
            int area = 0;
            for(int i=0; i<grid.length; i++){
                for(int j=0; j<grid[0].length; j++){
                    if(grid[i][j] == '1'){
                        area++;
                        dfs(grid, i, j);
                    }
                }
            }
            return area;
        }
    
        private void dfs(char[][] grid, int r, int c){
            if(!isArea(grid,r,c)){
                return;
            }
            if(grid[r][c] != '1'){
                return;
            }
            grid[r][c] = '2';
    
            dfs(grid, r-1, c);
            dfs(grid, r, c-1);
            dfs(grid, r+1, c);
            dfs(grid, r, c+1);
        }
    
        boolean isArea(char[][] grid, int r, int c){
            return 0<=r && r < grid.length 
                    && 0 <= c && c < grid[0].length;
        }
    }

  • 广度优先算法

    • class Solution {
          /**
          广度优先搜索bfs
          扫描整个二维网络，如果一个位置为1，加入队列，进行广度优先搜索
           */
          public int numIslands(char[][] grid) {
              if(grid == null || grid.length == 0){
                  return 0;
              }
      
              int nr = grid.length;
              int nc = grid[0].length;
              int nums_islands = 0;
      
              for(int r=0; r < nr; ++r){
                  for(int c = 0; c<nc; ++c){
                      if(grid[r][c] == '1'){
                          ++nums_islands;
                          grid[r][c] = '2';
                          Queue<Integer> neighbors = new LinkedList<>();
                          neighbors.add(r * nc + c);
                          while(!neighbors.isEmpty()){
                              int id = neighbors.remove();
                              int row = id / nc;
                              int col = id % nc;
                              if (row - 1 >= 0 && grid[row-1][col] == '1') {
                                  grid[row-1][col] = '2';
                                  neighbors.add((row-1) * nc + col);
                              }
                              if (row + 1 < nr && grid[row+1][col] == '1') {
                                  grid[row+1][col] = '2';
                                  neighbors.add((row+1) * nc + col);
                              }
                              if (col - 1 >= 0 && grid[row][col-1] == '1') {
                                  neighbors.add(row * nc + col-1);
                                  grid[row][col-1] = '2';
                              }
                              if (col + 1 < nc && grid[row][col+1] == '1') {
                                  neighbors.add(row * nc + col+1);
                                  grid[row][col+1] = '2';
                              }                      
                          }
                      }
                  }
              }
              return nums_islands;
          }

       

695. 岛屿的最大面积

• 🔗：695. 岛屿的最大面积 - 力扣（LeetCode）
• 思路：深度优先搜索
• 代码：

  class Solution {
      public int maxAreaOfIsland(int[][] grid) {
          if(grid.length==0||grid[0].length==0){
              return 0;
          }
  
          int res = 0;
          for(int r=0; r<grid.length; r++){
              for(int c=0; c<grid[0].length; c++){
                  if(grid[r][c]==1){
                      int a = area(grid, r, c);
                      res = Math.max(res,a);
                  }
              }
          }
          return res;
      }
  
      int area(int[][] grid, int r, int c){
          if (!(0 <= r && r < grid.length 
              && 0 <= c && c < grid[0].length)) {
              return 0;
          }
          if(grid[r][c] != 1){
              return 0;
          }
  
          grid[r][c] = 2;
          return 1 
              + area(grid, r-1, c)
              + area(grid, r+1, c)
              + area(grid, r, c-1)
              + area(grid, r, c+1);
      }
  }