算法打卡：第十一章 图论part03

今日收获：孤岛的总面积，沉没孤岛，水流问题，建造最大岛屿

1. 孤岛的总面积

题目链接：101. 孤岛的总面积

思路：只要岛屿中有一个节点是边缘节点，那么这个岛屿就不是孤岛，结果不累加其面积。在深度优先函数中总共有三个地方需要判断：

（1）当前传入节点是否是边缘节点

（2）在下个节点进行深度优先遍历之前，判断这个节点是否是边缘节点

（3）根据深度优先遍历的返回值判断，如果深度优先遍历的过程中出现了边缘节点，则当前岛屿也不是孤岛。

方法：

import java.util.Scanner;

public class Main{
    static int current;
    static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        int M=sc.nextInt();
        
        int[][] grid=new int[N][M];
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                grid[i][j]=sc.nextInt();
            }
        }
        
        boolean[][] visited=new boolean[N][M];
        int result=0;
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (!visited[i][j]&&grid[i][j]==1){
                    current=0;  // 当前岛屿的面积
                    visited[i][j]=true;
                    if (dfs(visited,i,j,grid)){  // 如果是孤岛
                        result+=current;
                    }
                }
            }
        }
        
        System.out.println(result);
        
    }
    
    public static boolean dfs(boolean[][] visited,int x,int y,int[][] grid){
        boolean flag=true;  // 是否为孤岛
        
        current++;  // 计算当前岛屿的面积
        
        if (x==0||y==0||x==grid.length-1||y==grid[0].length-1){
            flag=false;
        }
        
        for (int i=0;i<4;i++){
            int nextX=x+around[i][0];
            int nextY=y+around[i][1];
            
            if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){
                continue;
            }
            
            
            if (!visited[nextX][nextY]&&grid[nextX][nextY]==1){
                if (nextX==0||nextY==0||nextX==grid.length-1||nextY==grid[0].length-1){
                    flag=false;
                }
                
                visited[nextX][nextY]=true;
                if (!dfs(visited,nextX,nextY,grid)){
                    flag=false;
                }
            }
        }
        
        return flag;
    }
}

2. 沉没孤岛

题目链接：102. 沉没孤岛

思路：遍历格子的四条边，将边上相邻的陆地都标记为2。孤岛中的陆地还是原来的1。然后再把1变成0，2变成1，输出格子。（也可以看作是把不同的岛屿做了标记）

方法：

import java.util.Scanner;

public class Main{
    static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        int M=sc.nextInt();
        
        int[][] grid=new int[N][M];
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                grid[i][j]=sc.nextInt();
            }
        }
        
        boolean[][] visited=new boolean[N][M];
        
        // 从格子四周遍历陆地，标记为2
        for (int i=0;i<grid.length;i++){  // 第0列和最后一列
            if (!visited[i][0]&&grid[i][0]==1){
                dfs(visited,i,0,grid);
            }
            
            if (!visited[i][M-1]&&grid[i][M-1]==1){
                dfs(visited,i,M-1,grid);
            }
        }
        
        for (int j=0;j<M;j++){  // 第一行和最后一行
            if (!visited[0][j]&&grid[0][j]==1){
                dfs(visited,0,j,grid);
            }
            
            if (!visited[N-1][j]&&grid[N-1][j]==1){
                dfs(visited,N-1,j,grid);
            }
        }
        
        // 将孤岛变为0，即grid中为1的格子
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (grid[i][j]==1){
                    grid[i][j]=0;
                }
            }
        }
        
        // 将原来的岛屿变为1
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (grid[i][j]==2){
                    grid[i][j]=1;
                }
            }
        }
        
        // 输出
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                System.out.print(grid[i][j]+" ");
            }
            System.out.println(" ");
        }
        
    }
    
    public static void dfs(boolean[][] visited,int x,int y,int[][] grid){
        visited[x][y]=true;
        grid[x][y]=2;
      
        for (int i=0;i<4;i++){
            int nextX=x+around[i][0];
            int nextY=y+around[i][1];
            
            if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){
                continue;
            }
            
            
            if (!visited[nextX][nextY]&&grid[nextX][nextY]==1){
                dfs(visited,nextX,nextY,grid);
            }
        }
    }
}

3. 水流问题

题目链接：103. 水流问题

思路：从两组边界开始逆流而上，判断是否能到达其他格子。最后的结果是从两组边界出发逆流而上都能到达的格子。

方法：

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;

public class Main{
    static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        
        // 接收数据
        int N=sc.nextInt();
        int M=sc.nextInt();
        
        int[][] heights=new int[N][M];
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                heights[i][j]=sc.nextInt();
            }
        }
        
        // 两组边界分别能到达的点
        boolean[][] first=new boolean[N][M];
        boolean[][] second=new boolean[N][M];
        
        // 从两组边界开始逆流而上
        for (int i=0;i<N;i++){
            dfs(heights,first,i,0,Integer.MIN_VALUE);
            dfs(heights,second,i,M-1,Integer.MIN_VALUE);
        }
        
        for (int j=0;j<M;j++){
            dfs(heights,first,0,j,Integer.MIN_VALUE);
            dfs(heights,second,N-1,j,Integer.MIN_VALUE);
        }
        
        // 收集两组边界都能到达的格子
        List<int[]> result=new ArrayList<>();
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (first[i][j]&&second[i][j]){
                    result.add(new int[]{i,j});
                }
            }
        }
        
        // 输出结果
        for (int [] pair:result){
            System.out.println(pair[0]+" "+pair[1]);
        }
    }
    
    public static void dfs(int[][] heights,boolean[][] visited,int x,int y,int pre){
        // 判定合法性
        if (heights[x][y]<pre){
            return;  // 不能逆流而上
        }
        
        // 访问当前节点和相邻节点
        visited[x][y]=true;
        for (int i=0;i<4;i++){
            int nextX=x+around[i][0];
            int nextY=y+around[i][1];
            
            if (nextX<0||nextY<0||nextX>=heights.length||nextY>=heights[0].length){
                continue;
            }
            
            if (!visited[nextX][nextY]){
                dfs(heights,visited,nextX,nextY,heights[x][y]);
            }
        }
    }
}

4. 建造最大岛屿

题目链接：104. 建造最大岛屿

思路：

（1）同属于一个岛屿的格子用相同的数字标记，不同属于一个岛屿的格子标记不同。

（2）用map存储每个岛屿的编号和面积

（3）遍历格子中的0节点，判断其周围格子是否属于某一个岛屿，如果是则将周围岛屿的面积相加，结果遍历中相加结果的最大值

（4）注意：0节点的周围节点所属岛屿面积不能重复相加（周围四个节点其中可能有同属于一个岛屿的），要使用set集合存储相加过面积的岛屿编号

（5）如果格子中没有0节点，结果取所有岛屿面积的最大值（即最多只能变水为陆一次，没有就不变）

方法：

import java.util.Scanner;
import java.util.HashMap;
import java.util.HashSet;

public class Main{
    static int count=2;  // 岛屿编号
    static int current;  // 岛屿面积
    static int[][] around={{0,1},{-1,0},{0,-1},{1,0}};
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        int M=sc.nextInt();
        
        int[][] grid=new int[N][M];
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                grid[i][j]=sc.nextInt();
            }
        }
        
        // 记录岛屿编号和面积
        HashMap<Integer,Integer> map=new HashMap<>();
        boolean[][] visited=new boolean[N][M];
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (!visited[i][j]&&grid[i][j]==1){  // 开始遍历新的岛屿
                    current=0;
                    dfs(visited,i,j,grid);
                    map.put(count,current);
                    count++;
                }
            }
        }
        
        
        int result=0;
        // 遍历格子中的0，判断其周围有没有岛屿，有的话加上面积
        // 注意岛屿编号不能重复访问
        HashSet<Integer> set=new HashSet<>();
        for (int i=0;i<N;i++){
            for (int j=0;j<M;j++){
                if (grid[i][j]==0){
                    int area=1;
                    for (int k=0;k<4;k++){
                        int nextX=i+around[k][0];
                        int nextY=j+around[k][1];
                        
                        if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){
                            continue;
                        }
                        
                        if (map.containsKey(grid[nextX][nextY])&&!set.contains(grid[nextX][nextY])){
                            set.add(grid[nextX][nextY]);
                            area+=map.get(grid[nextX][nextY]);
                        }
                    }
                    result=Math.max(result,area);
                    set.clear();
                }
            }
        }
        
        // 如果格子中没有0，取岛屿的最大面积
        for (int key:map.keySet()){
            result=Math.max(result,map.get(key));
        }
        
        System.out.println(result);
    }
    
    public static void dfs(boolean[][] visited,int x,int y,int[][] grid){
        visited[x][y]=true;
        grid[x][y]=count;
        current++;
        
        for (int i=0;i<4;i++){
            int nextX=x+around[i][0];
            int nextY=y+around[i][1];
            
            if (nextX<0||nextY<0||nextX>=grid.length||nextY>=grid[0].length){
                continue;
            }
            
            if (!visited[nextX][nextY]&&grid[nextX][nextY]==1){
                dfs(visited,nextX,nextY,grid);
            }
        }
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/881682.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【数据库】常用数据库简介

【数据库】常用数据库简介

目录 &#x1f354; 常用的关系型数据库 &#x1f354; Mysql简介 &#x1f354; SQL 简介 SQL语句的分类 SQL 写法 SQL 常用的数据类型 &#x1f354; DDL语句 对数据库的操作 对数据表的操作 &#x1f354; DML语句 插入数据 insert into 修改数据 update 删除数…
阅读更多...
python实现多个pdf文件合并

python实现多个pdf文件合并

打印发票时&#xff0c;需要将pdf合并成一个&#xff0c;单页两张打印。网上一些pdf合并逐渐收费&#xff0c;这玩意儿都能收费&#xff1f;自己写一个脚本使用。 实现代码&#xff1a; 输入pdf文件夹路径data_dir&#xff0c;统计目录下的“合并后的PDF”文件夹下&#xff0c;…
阅读更多...
linux重要文件

linux重要文件

/etc/sysconfig/network-scripts/ifcfg-eth1 网卡重启 /etc/init.d/network restart ifup ethname & ifdown ethname /etc/resolv.conf 设置Linux本地的客户端DNS的配置文件 linux客户端DNS可以在网卡配置文件(/etc/sysconfig/network/ifcfg-eth0 DNS2)里配置 也可以在/et…
阅读更多...
Java_Day04学习

Java_Day04学习

类继承实例 package com.dx.test03; public class extendsTest {public static void main(String args[]) {// 实例化一个Cat对象&#xff0c;设置属性name和age&#xff0c;调用voice()和eat()方法&#xff0c;再打印出名字和年龄信息/********* begin *********/Cat cat ne…
阅读更多...
Pandas -----------------------基础知识（一）

Pandas -----------------------基础知识（一）

目录 Series对象 属性和方法 布尔值列表获取Series对象中部分数据 运算 DateFrame对象 常用属性 常见方法 运算 总结 Series对象 是DataFrame的列对象或者行对象 生成Series对象生成索引使用元组创建Series对象使用字典创建Series对象 通过Pandas创建对象 自定义索引 …
阅读更多...
面试官问：你最自豪的成就是什么？

面试官问：你最自豪的成就是什么？

当面试官问你最自豪的成就是什么&#xff0c;我们首先分析面试官为什么这么问&#xff0c;他想通过这问题得到什么信息&#xff1f; 你最自豪的成就是什么&#xff1f; 其实反应了一个人的职业驱动力&#xff0c;比如我们常说的&#xff1a;上进心&#xff0c;主动积极性&…
阅读更多...
【机器学习-监督学习】朴素贝叶斯

【机器学习-监督学习】朴素贝叶斯

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈Python机器学习 ⌋ ⌋ ⌋ 机器学习是一门人工智能的分支学科&#xff0c;通过算法和模型让计算机从数据中学习&#xff0c;进行模型训练和优化&#xff0c;做出预测、分类和决策支持。Python成为机器学习的首选语言&#xff0c;…
阅读更多...
【小沐学GIS】基于Openstreetmap创建Sionna RT场景（Python）

【小沐学GIS】基于Openstreetmap创建Sionna RT场景（Python）

文章目录 1、简介1.1 blender 2、下载和安装2.1 Python2.2 jupyter 3、运行结语 1、简介 1.1 blender https://www.blender.org/ Blender 是一款免费开源的3D创作套件。 使用 Blender&#xff0c;您可以创建3D可视化效果&#xff0c;例如静态图像、3D动画、VFX&#xff08;…
阅读更多...
【UE5】将2D切片图渲染为体积纹理，最终实现使用RT实时绘制体积纹理【第一篇-原理】

【UE5】将2D切片图渲染为体积纹理，最终实现使用RT实时绘制体积纹理【第一篇-原理】

如果想直接制作&#xff0c;请看【第二篇】内容 这次做一个这样的东西&#xff0c;通过在2DRT上实时绘制&#xff0c;生成动态的体积纹理&#xff0c;也就是可以runtime的VDB 设想的文章流程: 对原理进行学习制作体积渲染制作实时绘制 第一篇&#xff08;本篇&#xff09;是对“…
阅读更多...
【Rust练习】16.模式

【Rust练习】16.模式

文章题目来自&#xff1a;https://practice-zh.course.rs/pattern-match/patterns.html 1 &#x1f31f;&#x1f31f; 使用 | 可以匹配多个值, 而使用 … 可以匹配一个闭区间的数值序列 fn main() {} fn match_number(n: i32) {match n {// 匹配一个单独的值1 > println!(…
阅读更多...
【赵渝强老师】K8s中的Deployment控制器

【赵渝强老师】K8s中的Deployment控制器

K8s的Deployment将Pod部署成无状态的应用程序&#xff0c;它只关心Pod的数量、Pod更新方式、使用的镜像和资源限制等。由于是无状态的管理方式&#xff0c;因此Deployment中没有角色和顺序的概念&#xff0c;换句话说&#xff1a;Deployment中没有状态。   通过使用Deploymen…
阅读更多...
【远程调用PythonAPI-flask】

【远程调用PythonAPI-flask】

文章目录 前言一、Pycharm创建flask项目1.创建虚拟环境2.创建flask项目 二、远程调用PythonAPI——SpringBoot项目集成1.修改PyCharm的host配置2.防火墙设置3.SpringBoot远程调用PythonAPI 前言 解决Pycharm运行Flask指定ip、端口更改无效的问题 首先先创建一个新的flask项目&…
阅读更多...
C语言 | Leetcode C语言题解之第415题字符串相加

C语言 | Leetcode C语言题解之第415题字符串相加

题目&#xff1a; 题解&#xff1a; char* addStrings(char* num1, char* num2) {int i strlen(num1) - 1, j strlen(num2) - 1, add 0;char* ans (char*)malloc(sizeof(char) * (fmax(i, j) 3));int len 0;while (i > 0 || j > 0 || add ! 0) {int x i > 0 ?…
阅读更多...
Games101学习 - 着色

Games101学习 - 着色

本文主要讲述Games101中的着色部分。 文中将使用UE的UTexture2D接口&#xff0c;若不了解可以看这篇&#xff1a; https://blog.csdn.net/grayrail/article/details/142165442 1.面积比计算三角形坐标 通过三角形面积比可以得到三角形的坐标alpha、beta、gamma从而进行插值&a…
阅读更多...
ChatGPT 4o 使用指南 (9月更新)

ChatGPT 4o 使用指南 (9月更新)

首先基础知识还是要介绍得~ 一、模型知识&#xff1a; GPT-4o&#xff1a;最新的版本模型&#xff0c;支持视觉等多模态&#xff0c;OpenAI 文档中已经更新了 GPT-4o 的介绍&#xff1a;128k 上下文&#xff0c;训练截止 2023 年 10 月&#xff08;作为对比&#xff0c;GPT-4…
阅读更多...
【Linux笔记】虚拟机内Linux内容复制到宿主机的Window文件夹（文件）中

【Linux笔记】虚拟机内Linux内容复制到宿主机的Window文件夹（文件）中

一、共享文件夹 I、Windows宿主机上创建一个文件夹 目录&#xff1a;D:\Centos_iso\shared_files II、在VMware中设置共享文件夹 1、打开VMware Workstation 2、选择需要设置的Linux虚拟机&#xff0c;点击“编辑虚拟机设置”。 3、在“选项”标签页中&#xff0c;选择“共…
阅读更多...
Vue学习记录之三（ref全家桶）

Vue学习记录之三（ref全家桶）

ref、reactive是在 setup() 声明组件内部状态用的&#xff0c; 这些变量通常都要 return 出去&#xff0c;除了供 < template > 或渲染函数渲染视图&#xff0c;也可以作为 props 或 emit 参数 在组件间传递。它们的值变更可触发页面渲染。 ref &#xff1a;是一个函数&…
阅读更多...
前端组件库

前端组件库

vant2现在的地址 Vant 2 - Mobile UI Components built on Vue
阅读更多...
【学习笔记】手写Tomcat 四

【学习笔记】手写Tomcat 四

目录 一、Read 方法返回 -1 的问题 二、JDBC 优化 1. 创建配置文件 2. 创建工具类 3. 简化 JDBC 的步骤 三、修改密码 优化返回数据 创建修改密码的页面 注意 测试 四、优化响应动态资源 1. 创建 LoginServlet 类 2. 把登录功能的代码放到 LoginServlet 类 3. 创…
阅读更多...
【工具变量】科技金融试点城市DID数据集（2000-2023年）

【工具变量】科技金融试点城市DID数据集（2000-2023年）

时间跨度&#xff1a;2000-2023年数据范围&#xff1a;286个地级市包含指标&#xff1a; year city treat post DID&#xff08;treat*post&#xff09; 样例数据&#xff1a; 包含内容&#xff1a; 全部内容下载链接&#xff1a; 参考文献-pdf格式&#xff1a;https://…
阅读更多...
最新文章

Copyright @ 2022~2023