草庐IT

蓝桥杯（全球变暖dfs）

KJplant 2023-04-09 原文

蓝桥杯（全球变暖dfs）

import java.util.Scanner;

/**
 * 该题使用了深度优先算法dfs用于把相连的#号当成一块大陆，并通过数组记录下有几块大陆
 * dfs算法并不难，只要对用dfs处理过后留下的aes数组和sea数组进行处理得到结果即可
 * 我的思路就是
 * 1、sea数组记录源数据，然后判断是否被淹赋‘*’号记录
 * 2、aes数组使用dfs算法把第一块大陆标记为1，第二块标记为2，以此类推
 * 3、最后假设num块大陆全部被淹，遍历sea数组如果有‘#’号则判断是第几块大陆，没有重复就使num减一
 * 4、最后输出num为最终结果
 */

public class test1 {
    static char[][] sea;//用于记录用例
    static int[][] aes;//用于记录不同的大陆，其值为不同大陆的标记
    static int n;//输入的初值
    static int num=0;//最后被淹没的大陆数量
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        sea = new char[n][n];
        aes = new int[n][n];
        //初始化sea
        for(int i=0;i<n;i++){
            sea[i] = scan.next().toCharArray();
        }
        //给aes初值全部赋0
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++)
              aes[i][j]=0;

        for(int i=0;i<n;i++){
            for (int j=0;j<n;j++){
                if(sea[i][j]=='#'){
                    if(aes[i][j]==0) {
                        num++;
                        dfs(i, j);//当检测到陆地就使用dfs()方法赋值
                    }
                    if(submerge(i,j))
                        sea[i][j]='*';//使用sunmerge方法判断是否会被淹没，被淹没就赋‘*’
                }
            }
        }
        //目前已知有num块陆地，使用数组land[]记录下还未被淹的陆地
        int[] land = new int[num];
        for(int i=0;i<num;i++)
            land[i]=1;
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                if(sea[i][j]=='#'){//当有被还未被淹没的陆地时
                    int x=aes[i][j]-1;
                    if(land[x]!=0){//此陆地还未被记录就把land赋0，淹没的陆地数num-1
                        land[x]=0;
                        num--;
                    }
                }
            }
        System.out.println(num);
    }

    static int[] x = {0,1,0,-1};
    static int[] y = {1,0,-1,0};
    //判断是否会被淹没，淹没返回true，否则返回false
    public static boolean submerge(int a, int b){
        for(int i=0;i<4;i++){
            if(a+y[i]>=0 && a+y[i]<n && b+x[i]>=0 && b+x[i]<n && sea[a+y[i]][b+x[i]]=='.')
                return true;
        }
        return false;
    }
    //DFS深度优先，把所在的大陆通过dfs都标记上记号num如:
    /*
    sea[][]: ....   aes[][]:0000
             .##.           0110
             ....           0000
     */
    public static void dfs(int a,int b){
        aes[a][b]=num;
        for(int i=0;i<4;i++){
            if(a+y[i]>=0 && a+y[i]<n && b+x[i]>=0 && b+x[i]<n && sea[a+y[i]][b+x[i]]=='#'&&aes[a+y[i]][b+x[i]]==0)
                dfs(a+y[i],b+x[i]);
        }
    }
}
蓝桥dfsampintstatic

有关蓝桥杯（全球变暖dfs）的更多相关文章

  1. 蓝桥杯备赛（二） - 2

    目录前言： 一、ASC分析代码实现二、 卡片分析代码实现三、 直线分析代码实现四、货物摆放分析代码实现小结：前言：  在刷题的过程中，发现蓝桥杯的题目和力扣的差别很大。让人有一种不一样的感觉，蓝桥杯题目偏向对于实际问题用编程去的解决，而力扣给人感觉很锻炼自己的编程思维，逻辑能力。两者结合去刷，相信会有不一样的收获。 一、ASC  已知大写字母A的ASCII码为65，请问大写字母L的ASCII码是多少？分析  这道题目看上去很简单，我们需确定自己计算的准确，所以我建议用编程去解决。代码实现publicclassTest8{publicstaticvoidmain(String[]args){Sy

  2. 酷早报：10月21日全球Web3加密行业重大资讯大汇总 - 2

    2022年10月21日星期五【数据指标】加密货币总市值：$0.95万亿BTC市值占比：38.51%恐慌贪婪指数：23极度恐慌 【今日快讯】1、【政讯】1.1.1、美联储布拉德：市场预期美联储11月会加息75个基点1.1.2、美联储哈克：将维持加息一段时间1.2、美国10年期国债收益率触及4.197%，为2008年6月以来最高1.3、法国数字转型部长：政府将专注于DeFi和Web31.4、巴西ATM机将于11月3日起支持USDT1.5、美众议院副议长将于11月初加入a16zCrypto担任政府事务主管1.6、香港数字资产托管机构FirstDigitalTrust首席执行官：香港仍是安全

  3. 蓝桥杯C/C++VIP试题每日一练之报时助手 - 2

    ?作者主页：静Yu?简介：CSDN全栈优质创作者、华为云享专家、阿里云社区博客专家，前端知识交流社区创建者?社区地址：前端知识交流社区?博主的个人博客：静Yu的个人博客?博主的个人笔记本：前端面试题个人笔记本只记录前端领域的面试题目，项目总结，面试技巧等等。接下来会更新蓝桥杯官方系统基础练习的VIP试题，依然包括解题思路，源代码等等。问题描述：给定当前的时间，请用英文的读法将它读出来。时间用时h和分m表示，在英文的读法中，读一个时间的方法是：　　如果m为0，则将时读出来，然后加上“o’clock”，如3:00读作“threeo’clock”。　　如果m不为0，则将时读出来，然后将分读出来，如5

  4. NEUQ-acm 预备队训练Week4—BFS/DFS - 2

    1.深度优先搜索(DFS)深度优先遍历主要思路是从图中一个未访问的顶点V开始，沿着一条路一直走到底，然后从这条路尽头的节点回退到上一个节点，再从另一条路开始走到底…，不断递归重复此过程，直到所有的顶点都遍历完成。例题P1605迷宫题目描述给定一个N×MN\timesMN×M方格的迷宫，迷宫里有TTT处障碍，障碍处不可通过。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。输入格式第一行为三个正整数N,M,TN,M,TN,M,T，分别表示迷宫的长宽和障碍总数。第二行为四个正整数SX,S

  5. 常见搜索模板DFS+BFS+二分搜索【算法】 - 2

     本篇讲的是常见的搜索模板，搜索题的解法时比较固定的，只要把模板记熟，加上自己找几道习题练习体会后，相信各位下次遇到这类题一定能拿下！！下面我将已典型的题目为例子介绍几种常见的搜索方式。 1.二分搜索二分搜索代码模板：例题：#includeusingnamespacestd;doublen;constdoubleeps=1e-12;//二分搜索intmain(){ intt; cin>>t; while(t--){ cin>>n; doublel=0,r=100000,res=-1; while(ln)r=mid-0.0001; elseif(mid*mid*mid二分搜索是只能对有

  6. 十四届蓝桥青少组模拟赛Python-20221108 - 2

    十四届蓝桥青少组模拟赛Python-20221108T1.二进制位数十进制整数2在十进制中是1位数，在二进制中对应10，是2位数。十进制整数22在十进制中是2位数，在二进制中对应10110，是5位数。请问十进制整数2022在二进制中是几位数？print(len(bin(2022))-2)#运行结果：11T2.晨跑小蓝每周六、周日都晨跑，每月的1、11、21、31日也晨跑。其它时间不晨跑。已知2022年1月1日是周六，请问小蓝整个2022年晨跑多少天？#样例代码1ls=[0,31,28,31,30,31,30,31,31,30,31,30,31]ans=0k=6foriinrange(1,13)

  7. 蓝桥杯 stm32 MCP4017 - 2

    本文代码使用HAL库。文章目录前言一、MCP4017的重要特性二、MCP4017计算RBW阻值三、MCP4017地址四、MCP4017读写函数五、CubeMX创建工程（利用ADC测量MCP4017电压）、对应代码：总结前言一、MCP4017的重要特性蓝桥杯板子上的是MCP4017T-104ELT，如图1。MCP4017是一个可编程电阻，通过写入的数值可以改变电阻的大小。重点在于6引脚（W），5引脚（B&#

  8. [蓝桥杯单片机]学习笔记——串口通信的基本原理与应用 - 2

    目录一、原理部分1、什么是串行通信（1）并行通信与串行通信（2）串行通信的制式（3）串行通信的主要方式  2、配置串口（1）SCON和PCON：串行口1的控制寄存器（2）SBUF：串行口数据缓冲寄存器 （3）AUXR：辅助寄存器​编辑（4）ES、PS：与串行口1中断相关的寄存器（5）波特率设置  3、串口框架编写二、程序案例一、原理部分1、什么是串行通信（1）并行通信与串行通信微控制器与外部设备的数据通信，根据连线结构和传送方式的不同，可以分为两种：并行通信和串行通信。并行通信：数据的各位同时发送与接收，每个数据位使用一条导线，这种方式传输快，但是需要多条导线进行信号传输。串行通信：数据一位一

  9. 考勤刷卡 最大和 简单 蓝桥杯省赛 2022 - 2

    问题描述小蓝负责一个公司的考勤系统,他每天都需要根据员工刷卡的情况来确定每个员工是否到岗。当员工刷卡时,会在后台留下一条记录,包括刷卡的时间和员工编号,只要在一天中员工刷过一次卡,就认为他到岗了。现在小蓝导出了一天中所有员工的刷卡记录,请将所有到岗员工的员工编号列出。输入格式输入的第一行包含一个正整数n,表示一天中所有员工的刷卡记录的条数。接下来n行,每行包含一条刷卡记录,每条刷卡记录的格式为:HH:MM:SSID其中HH:MM:SS表示刷卡时间,HH为一个0到23之间的两位十进制整数(可能含前导0)表示时,MM为一个0到59之间的两位十进制整数(可能含前导0)表示分,SS为一个0到59之间的

  10. 字符串的特殊读取——基于蓝桥杯两道题目（C/C++) - 2

    目录1 例题1.1 卡片换位1.2 人物相关性分析2 字符串的读取2.1 综述2.2 scanf2.3  getline/getchar/get2.4 注意2.5 说明3 C语言中字符串有关问题3.1 常用函数3.2 使用实例3.3 附一些函数先看例题1 例题1.1 卡片换位问题描述你玩过华容道的游戏吗？这是个类似的，但更简单的游戏。看下面3x2的格子在其中放5张牌，其中A代表关羽，B代表张飞，*代表士兵。还有一个格子是空着的。你可以把一张牌移动到相邻的空格中去(对角不算相邻)。游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。输入格式：输入两行6个字符表示当前的局面输出格式：一个整

随机推荐