当前位置: 首页 > article >正文

图论part3|101.孤岛的总面积、沉没孤岛、417. 太平洋大西洋水流问题

101. 孤岛的总面积

  • 🔗:101. 孤岛的总面积
  • 思路:和昨天的岛的区别是:是否有挨着边的岛屿
    • 所以可以先遍历四条边挨着的岛屿,把他们标记为非孤岛
    • 再计算其他岛屿当中的最大面积
  • 代码:(深度搜索)
  • import java.util.*;
    /*
        思路:
        和岛的区别是:是否有挨着边的岛屿
        --所以可以先遍历四条边挨着的岛屿,把他们标记为非孤岛
        --再计算其他岛屿当中的最大面积
    */
    public class Main{
        
        public static int count = 0;
    
        public static void dfs(int[][] matrix,int i,int j, int aim){
            // 终止条件
            if(i>=matrix.length || i<0 || j<0 || j>=matrix[0].length) return;
            if(matrix[i][j]!=1) return;
            // mark
            matrix[i][j] = aim;
            count++;
            // 遍历
            dfs(matrix, i, j-1, aim);
            dfs(matrix, i, j+1, aim);
            dfs(matrix, i-1, j, aim);
            dfs(matrix, i+1, j, aim);
    
        }
        public static void main(String[] args){
            // N M
            Scanner scanner = new Scanner(System.in);
            int row = scanner.nextInt();
            int col = scanner.nextInt();
            int[][] matrix = new int [row][col];
            for(int i=0; i<row; i++){
                for(int j=0; j<col; j++){
                    matrix[i][j] = scanner.nextInt();
                }
            }
            // dfs
            for(int i=0; i<row; i++){
                if(matrix[i][0]==1)
                    dfs(matrix, i, 0, 2);
                if(matrix[i][col-1]==1)
                    dfs(matrix, i, col-1,2);
            }
    
            for(int j=0; j<col; j++){
                if(matrix[0][j]==1)
                    dfs(matrix,0,j,2);
                if(matrix[row-1][j] == 1)
                    dfs(matrix,row-1,j,2);
            }
    
            count=0;
            for(int i=1; i<row; i++){
                for(int j=1; j<col; j++){
                    if(matrix[i][j]==1){
                        dfs(matrix, i, j, 3);
                    }
                }
            }
            System.out.println(count);
    
        }
    
    }

  • 代码:广度搜索
import java.util.*;
/*
    思路:
    和岛的区别是:是否有挨着边的岛屿
    --所以可以先遍历四条边挨着的岛屿,把他们标记为非孤岛
    --再计算其他岛屿当中的最大面积
*/
public class Main{
    
    public static int count = 0;
    private static final int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};

    public static void bfs(int[][] matrix,int r,int c, int aim){
        // queue, linkedlist
        // method: poll. add. isEmpty
        Queue<int[]> que = new LinkedList<>();
        que.add(new int[]{r,c});
        matrix[r][c] = aim;
        count++;
        while(!que.isEmpty()){
            int[] cur = que.poll();
            int row = cur[0];
            int col = cur[1];
            for(int i=0; i<4; i++){
                int nr = row + dir[i][0];
                int nc = col + dir[i][1];
                if(nr<0||nc<0||nr>=matrix.length||nc>=matrix[0].length)
                continue;
                if(matrix[nr][nc]==1){
                    que.add(new int[]{nr,nc});
                    count++;
                    matrix[nr][nc] = aim;
                }
            }

        }

    }
    public static void main(String[] args){
        // N M
        Scanner scanner = new Scanner(System.in);
        int row = scanner.nextInt();
        int col = scanner.nextInt();
        int[][] matrix = new int [row][col];
        for(int i=0; i<row; i++){
            for(int j=0; j<col; j++){
                matrix[i][j] = scanner.nextInt();
            }
        }
        // bfs
        for(int i=0; i<row; i++){
            if(matrix[i][0]==1)
                bfs(matrix, i, 0, 2);
            if(matrix[i][col-1]==1)
                bfs(matrix, i, col-1,2);
        }

        for(int j=0; j<col; j++){
            if(matrix[0][j]==1)
                bfs(matrix,0,j,2);
            if(matrix[row-1][j] == 1)
                bfs(matrix,row-1,j,2);
        }

        count=0;
        for(int i=1; i<row; i++){
            for(int j=1; j<col; j++){
                if(matrix[i][j]==1){
                    bfs(matrix, i, j, 3);
                }
            }
        }
        System.out.println(count);

    }

}

102. 沉没孤岛

  • 🔗:102. 沉没孤岛
  • 思路:感受不到和上一题太大的区别
  • 代码:(dfs)
    • import java.util.*;
      /*
          思路:
          
      */
      public class Main{
           
       
          public static void dfs(int[][] matrix,int i,int j, int aim){
              // 终止条件
              if(i>=matrix.length || i<0 || j<0 || j>=matrix[0].length) return;
              if(matrix[i][j]!=1) return;
              // mark
              matrix[i][j] = aim;
              // 遍历
              dfs(matrix, i, j-1, aim);
              dfs(matrix, i, j+1, aim);
              dfs(matrix, i-1, j, aim);
              dfs(matrix, i+1, j, aim);
       
          }
          public static void main(String[] args){
              // N M
              Scanner scanner = new Scanner(System.in);
              int row = scanner.nextInt();
              int col = scanner.nextInt();
              int[][] matrix = new int [row][col];
              for(int i=0; i<row; i++){
                  for(int j=0; j<col; j++){
                      matrix[i][j] = scanner.nextInt();
                  }
              }
              // dfs
              for(int i=0; i<row; i++){
                  if(matrix[i][0]==1)
                      dfs(matrix, i, 0, 2);
                  if(matrix[i][col-1]==1)
                      dfs(matrix, i, col-1,2);
              }
       
              for(int j=0; j<col; j++){
                  if(matrix[0][j]==1)
                      dfs(matrix,0,j,2);
                  if(matrix[row-1][j] == 1)
                      dfs(matrix,row-1,j,2);
              }
       
              for(int i=0; i<row; i++){
                  for(int j=0; j<col; j++){
                      if(matrix[i][j] == 2)
                         System.out.print(1+" ");
                      else
                          System.out.print(0 + " "); 
                  }
                  System.out.print("\n");
              }
       
          }

417. 太平洋大西洋水流问题

  • 🔗:
    417. 太平洋大西洋水流问题https://leetcode.cn/problems/pacific-atlantic-water-flow/
  • 思路:
    • 这一题题目有一点难以理解,当时大体上有了前两题的铺垫还是比较好做的。
    • 题意大概是:左上两条边连接pacific,右下两条边连接Atlantic,雨水可以流向小于等于高度的方向(东南西北),求同时可以流向太平洋和大西洋的方块。
    • 这题可以分成两部分来看,首先找到可以流向pacific的点,然后找到可以流向Atlantic的点,求它们的交集。
      • 存储方式:我一开始想到的是用三维数组进行存储,当时两个二维数组的方式可能更好写一些(没有太大区别)
    • 遍历方式:采用深度优先遍历,遍历过的点都设置为true(有一点像岛屿问题),如果不能延伸则return(返回条件,即相邻岛屿高度<目前岛屿高度)
  • 代码:
    • class Solution {
          static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
          int[][] heights;
          int m,n;
      
          public List<List<Integer>> pacificAtlantic(int[][] heights) {
              this.heights = heights;
              this.m = heights.length;
              this.n = heights[0].length;
              boolean[][] pacific = new boolean[m][n];
              boolean[][] atlantic = new boolean[m][n];
              for(int i=0; i<m; i++){
                  dfs(i, 0, pacific);
              }    
               for(int i=0; i<m; i++){
                  dfs(i, n-1, atlantic);
              }
              for(int j=1; j<n;j++){
                  dfs(0,j,pacific);
              }           
              for(int j=0; j<n-1; j++){
                  dfs(m-1,j,atlantic);
              }
              List<List<Integer>> result = new ArrayList<>();
              for(int i=0; i<m; i++){
                  for(int j=0; j<n; j++){
                      if(pacific[i][j] && atlantic[i][j]){
                          List<Integer> cell = new ArrayList<>();
                          cell.add(i);
                          cell.add(j);
                          result.add(cell);
                      }
                  }
              }
              return result;
          }
      
          public void dfs(int row, int col, boolean[][] ocean){
              if(ocean[row][col]) return;
              ocean[row][col] = true;
              for(int[] dir:dirs){
                  int newRow = row + dir[0];
                  int newCol = col + dir[1];
                  if(newRow>=0 && newCol>=0 && newRow<m && newCol<n && heights[newRow][newCol]>=heights[row][col]){
                      dfs(newRow, newCol, ocean);
                  }
              }
          }
      }


http://www.kler.cn/a/589937.html

相关文章:

  • Vue3项目匹配PC端和移动端---一套组件
  • MATLAB语言的编程竞赛
  • 沉浸式vr大空间打造,打造超真实的虚拟体验
  • 【教学类-43-25】20240311 数独3宫格的所有可能(图片版 12套样式,空1格-空8格,每套510张,共6120小图)
  • 配置 VSCode 的 C# 开发环境
  • Matlab 基于专家pid控制的时滞系统
  • Tree of Thought Prompting(思维树提示)
  • 如何在 K8s 内部实现安全的网络隔离?
  • 掌握Python项目的依赖管理:利用`venv`与`conda`高效创建虚拟环境
  • 深度解析ECharts.js:构建现代化数据可视化的利器
  • c++图论(一)之图论的起源和图的概念
  • 【MySQL】MySQL审计工具Audit Plugin安装使用
  • 工作记录 2017-01-25
  • 树莓派上的 TensorFlow Lite:从零开始的摄像头图像识别
  • python-数据结构汇总,树图、代码讲解(字符串、数组、字典、集合、元组)
  • 5分钟快速申请一个EDU教育邮箱
  • Qt选择文件路径,并写入文件
  • 华为hcia——Datacom实验指南——Ping和Tracert的工作原理
  • 【自学笔记】Solidity基础知识点总览-持续更新
  • Excel导出工具类--复杂的excel功能导出(使用自定义注解导出)