PTA L2-048 寻宝图

这篇具有很好参考价值的文章主要介绍了PTA L2-048 寻宝图。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

L2-048 寻宝图

题目描述

给定一幅地图,其中有水域,有陆地。被水域完全环绕的陆地是岛屿。有些岛屿上埋藏有宝藏,这些有宝藏的点也被标记出来了。本题就请你统计一下,给定的地图上一共有多少岛屿,其中有多少是有宝藏的岛屿。

输入格式

输入第一行给出 2 2 2个正整数 N N N M M M ( 1 < N × M ≤ 1 e 5 ) (1<N×M≤1e5 ) 1<N×M1e5,是地图的尺寸,表示地图由 N N N M M M 列格子构成。随后 N N N 行,每行给出 M M M 位个位数,其中 0 0 0 表示水域, 1 1 1 表示陆地,2-9 表示宝藏。
注意:两个格子共享一条边时,才是“相邻”的。宝藏都埋在陆地上。默认地图外围全是水域。

输出格式

在一行中输出 2 个整数,分别是岛屿的总数量和有宝藏的岛屿的数量。

输入样例

10 11
01000000151
11000000111
00110000811
00110100010
00000000000
00000111000
00114111000
00110010000
00019000010
00120000001

输出样例

7 2

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector<int>f[N],st[N];
int cnt,sum;
bool flag;
int n,m;
int dx[] = {-1,0,1,0},dy[] = {0,1,0,-1};
void dfs(int x,int y)
{
    st[x][y] = true;
    if(f[x][y] > 1) flag = true;
    for(int i = 0;i < 4;i++)
    {
        int xx = x + dx[i],yy = y + dy[i];
        if(xx >= 1 && xx <= n&&yy >= 1&&yy <= m&&f[xx][yy]&&!st[xx][yy])
        {
            if(f[xx][yy] > 1) flag = true;
            dfs(xx,yy);
        }
    }
}
int main()
{
    cin>>n>>m;
    for(int i = 1;i <= n;i++)
    {
        f[i].push_back(0);
        st[i].push_back(0);
        for(int j = 1;j <= m;j++)
        {
            char c;
            cin>>c;
            f[i].push_back(c-'0');
            st[i].push_back(0);
        }
    }
    for(int i = 1;i <= n;i++)
        for(int j = 1;j <= m;j++)
        {
            if(f[i][j] && !st[i][j])
            {
                flag = false;
                sum++;
                dfs(i,j);
                if(flag) cnt++;
            }
        }
    cout<<sum<<" "<<cnt;
    return 0;
}

这里需要用vector来存,n*m <= 1e5,二维数组只能开到1e4。
本来想着数据可能很弱,打算直接用二维数组卡过去(/≧▽≦)/,结果被卡了一个点(24分)/(ㄒoㄒ)/~~。
回到这道题,就是一个连通块问题,写个dfs或者bfs就行了,所以这题关键是要想到用vector。文章来源地址https://www.toymoban.com/news/detail-430882.html

到了这里,关于PTA L2-048 寻宝图的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • PTA L2-043 龙龙送外卖

    龙龙是“饱了呀”外卖软件的注册骑手,负责送帕特小区的外卖。帕特小区的构造非常特别,都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树,根结点是外卖站,树上的结点就是要送餐的地址。 每到中午 12 点,帕特小区就进入了点餐高峰。一开始,

    2023年04月22日
    浏览(33)
  • PTA L2-043龙龙送外卖

    4.1.6 L2-043龙龙送外卖 题目地址:https://pintia.cn/problem-sets/994805046380707840/exam/problems/1518582482059845632 题目概述: 这是一道关于求树中各个结点深度的题,两种方法:用DFS(将输入转为孩子表示法);用回溯法(从结点往上找双亲结点统计出结点的距离)。题目每新增一个外卖点

    2024年02月03日
    浏览(33)
  • PTA L2-045 堆宝塔 (25 分)

    堆宝塔游戏是让小朋友根据抓到的彩虹圈的直径大小,按照从大到小的顺序堆起宝塔。但彩虹圈不一定是按照直径的大小顺序抓到的。聪明宝宝采取的策略如下: 首先准备两根柱子,一根 A 柱串宝塔,一根 B 柱用于临时叠放。 把第 1 块彩虹圈作为第 1 座宝塔的基座,在 A 柱

    2023年04月24日
    浏览(36)
  • 2023 PTA天梯赛补题(L1 & L2)

    输入输出题 输入输出题 k == n 和 k == m 分别输出,题目怎么说就怎么做 判断一下c 等于a + b还是a*b或者都不是,分别按要求输出 针对每一群玩游戏的宝宝,枚举判断一下就好了 写的有点烦,基本就是一步一步模拟,思路在注释里写了 枚举分配方案,代码中a代表女生寝室的数

    2024年02月03日
    浏览(40)
  • PTA(C语言)本题要求编写程序,求一个给定的m×n矩阵各行元素之和。

    本题要求编写程序,求一个给定的m×n矩阵各行元素之和。 输入格式: 输入第一行给出两个正整数m和n(1≤m,n≤6)。随后m行,每行给出n个整数,其间 以空格分隔。 输出格式: 每行输出对应矩阵行元素之和。 输入样例: 输出样例:  

    2024年02月03日
    浏览(42)
  • 题目:2185.统计包含给定前缀的字符串

    ​​ 题目来源:         leetcode题目,网址:2185. 统计包含给定前缀的字符串 - 力扣(LeetCode) 解题思路:        遍历判断即可。 解题代码: 总结:         官方题解也是一样的思路。

    2024年02月15日
    浏览(56)
  • (Java)数据结构——排序(第一节)堆排序+PTA L2-012 关于堆的判断

    本博客是博主用于复习数据结构以及算法的博客,如果疏忽出现错误,还望各位指正。 堆排序是一种基于堆数据结构的排序算法,其核心思想是将待排序的序列构建成一个最大堆(或最小堆),然后将堆顶元素与最后一个元素交换,再将剩余元素重新调整为最大堆(或最小堆

    2024年04月12日
    浏览(40)
  • 浙大版PTA《Python 程序设计》题目集 参考答案

    本答案配套详解教程专栏,欢迎订阅: PTA浙大版《Python 程序设计》题目集 详解教程_少侠PSY的博客-CSDN博客

    2024年02月08日
    浏览(66)
  • 【PTA题目】7-11 求矩阵的局部极大值 分数 15

    7-11 求矩阵的局部极大值 分数 15 全屏浏览题目 切换布局 作者 徐镜春 单位 浙江大学 给定M行N列的整数矩阵A,如果A的非边界元素A[i][j]大于相邻的上下左右4个元素,那么就称元素A[i][j]是矩阵的局部极大值。本题要求给定矩阵的全部局部极大值及其所在的位置。 输入格式:

    2024年02月04日
    浏览(42)
  • PTA(浙大版《C语言程序设计(第3版)》题目集

    学习C语言程序设计的PTA题目 本题要求编写程序,计算4个整数的和与平均值。题目保证输入与输出均在整型范围内。 输入格式: 输入在一行中给出4个整数,其间以空格分隔。 输出格式: 在一行中按照格式“Sum = 和; Average = 平均值”顺序输出和与平均值,其中平均值精确到小数

    2024年01月18日
    浏览(69)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包