AcWing 4510. 寻宝!大冒险!(暴力枚举)

news/2024/5/19 1:34:54 标签: 算法, c++, 蓝桥杯, 枚举

题目如下:

在这里插入图片描述
在这里插入图片描述

输入样例1:

5 100 2
0 0
1 1
2 2
3 3
4 4
0 0 1
0 1 0
1 0 0

输出样例1:

3

样例 1 1 1 解释

绿化图上 ( 0 , 0 ) (0,0) (0,0) ( 1 , 1 ) (1,1) (1,1) ( 2 , 2 ) (2,2) (2,2) 三处均可能埋有宝藏。

输入样例2:

5 4 2
0 0
1 1
2 2
3 3
4 4
0 0 0
0 1 0
1 0 0

输出样例2:

0

样例 2 2 2 解释

如果将藏宝图左下角与绿化图 ( 3 , 3 ) (3,3) (3,3) 处对应,则藏宝图右上角会超出绿化图边界,对应不成功。

题解 or 思路:

题目中说:
特别地,藏宝图左下角位置一定是一棵树,即 A [ x ] [ y ] = B [ 0 ] [ 0 ] = 1 A[x][y]=B[0][0]=1 A[x][y]=B[0][0]=1,表示了宝藏埋藏的位置。

所以,我们可以枚举左下角, 然后检查是否合法,如果合法答案 + 1 + 1 +1

AC 代码如下:

const int N = 1009;
int n, l, s;
int x[N], y[N], b[N][N];
void solve()
{
    cin >> n >> l >> s;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];
    
    int one = 0;
    for (int i = s; i >= 0; i--)
        for (int j = 0; j <= s; j++)
            cin >> b[i][j], one += b[i][j];

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        if (x[i] + s > l || y[i] + s > l)
            continue;
        int cnt = 0;
        for (int j = 1; j <= n; j++)
        {
            if (cnt == -1)
                break;
            if (x[j] >= x[i] && x[j] <= x[i] + s && y[j] >= y[i] && y[j] <= y[i] + s)
            {
                b[x[j] - x[i]][y[j] - y[i]] ? cnt++ : cnt = -1;
            }
        }
        ans += (cnt == one ? 1 : 0);
    }
    cout << ans << '\n';
}
int main()
{
    solve();
}

http://www.niftyadmin.cn/n/27858.html

相关文章

云原生|kubernetes|2022年底cks真题解析(11-16)

前言&#xff1a; 接上一篇文章&#xff1a;云原生|kubernetes|2022年底cks真题解析&#xff08;1-10&#xff09;_晚风_END的博客-CSDN博客 2022年底的csk真题第二部分 11题到16题 十一&#xff0c; Trivy 扫描镜像安全漏洞 题目&#xff1a; Task 使用 Trivy 开源容器扫…

解决d2l包下载不了的问题

目录 关于d2l包 1、在pypi网站的找到d2l包 2、cmd下载文件 3、检测d2l包的下载是否成功 4、在虚拟环境中完成安装 关于d2l包 d2l包是李沐老师等人开发的《动手深度学习》配套的包&#xff0c;最初的时候&#xff0c;我并没有安装的想法&#xff0c;可在代码实现方面&…

基于uds和modbus协议的bootloader对比

2022年参与了两个bootloader项目的开发&#xff0c;两个项目使用的芯片、通讯驱动不同&#xff0c;因此传输协议也不同&#xff0c;年底了将两个项目做一个对比&#xff0c;也顺便加深下对bootloader的理解。相同点&#xff1a;modbusuds刷新流程刷新流程大同小异&#xff0c;简…

acwing86场周赛题解(模拟,dp,数学推导式)

目录 第一题&#xff1a;AcWing 4794. 健身 思路 核心代码 完整代码 第二题&#xff1a;4795. 安全区域 思路 核心代码 完整代码 第三题&#xff1a;4796. 删除序列 思路 核心代码 完整代码 谢谢您的阅读 第一题&#xff1a;AcWing 4794. 健身 4794. 健身 李华…

缺省参数!C++教你如何成为一名优秀的舔狗

&#x1f451;专栏内容&#xff1a;C学习笔记⛪个人主页&#xff1a;子夜的星的主页&#x1f495;座右铭&#xff1a;日拱一卒&#xff0c;功不唐捐 目录一、前言二、缺省参数1、缺省参数的定义2、缺省参数的分类Ⅰ、全缺省参数Ⅱ、半缺省参数三、注意事项1、直给中间的参数传参…

Vector - VT System - 模拟IO板卡_VT2816

前面介绍了模拟量的输入板卡VT2004&#xff0c;今天我们介绍的这个板卡依然是模拟量的输入&#xff0c;具体使用场景可能要我们根据实际的使用场景去进行选择。VT2004更偏向于激励&#xff0c;而VT2816更偏向于通用模拟量的IO使用&#xff0c;下面我们从功能、参数、硬件结构等…

基于Vue框架的web项目实现同一个浏览器仅能同时登录一个账号的方法

文章目录1、同一个浏览器仅能同时登录一个账号的场景2、同一个浏览器同时登录多个账号存在的问题3、同一个浏览器仅能同时登录一个账号的实现方法1、同一个浏览器仅能同时登录一个账号的场景 基于Vue框架的web项目需要实现同一个浏览器只允许登录一个账号&#xff0c;即如果已…

Linux进程控制(进程退出+进程等待)

目录 一、子进程创建 1.1 fork函数深入 1.2 写时拷贝 二、进程退出 2.1.1 进程退出码概念 2.1.2 系统退出码文字描述 2.1.3 _exit和exit函数 2.1.4 查看退出码 三、进程等待 3.1 进程等待解决僵尸进程 3.2 进程等待方法 3.2.1 wait 3.2.2 waitpid(&#xff09; 四、…