【NOIP提高组】引水入城

【NOIP提高组】引水入城


💐The Begin💐点点关注,收藏不迷路💐

在这里插入图片描述

在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊,刚好构成一个N行M列的矩形,如上图所示,其中每个格子都代表一座城 市,每座城市都有一个海拔高度。 为了使居民们都尽可能饮用到清澈的湖水,现在要在某些城市建造水利设施。水利设施 有两种,分别为蓄水厂和输水站。蓄水厂的功能是利用水泵将湖泊中的水抽取到所在城市的 蓄水池中。因此,只有与湖泊毗邻的第1行的城市可以建造蓄水厂。而输水站的功能则是通 过输水管线利用高度落差,将湖水从高处向低处输送。故一座城市能建造输水站的前提,是 存在比它海拔更高且拥有公共边的相邻城市,已经建有水利设施。 由于第N行的城市靠近沙漠,是该国的干旱区,所以要求其中的每座城市都建有水利 设施。那么,这个要求能否满足呢?如果能,请计算最少建造几个蓄水厂;如果不能,求干 旱区中不可能建有水利设施的城市数目。

输入

输入的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N和M,表示矩形的规模。 接下来N行,每行M个正整数,依次代表每座城市的海拔高度。输入的每行中两个数之间用一个空格隔开。 输入的第一行是两个正整数N和M,表示矩形的规模。 接下来N行,每行M个正整数,依次代表每座城市的海拔高度。

输出

输出有两行。如果能满足要求,输出的第一行是整数1,第二行是一个整数,代表最少 建造几个蓄水厂;如果不能满足要求,输出的第一行是整数0,第二行是一个整数,代表有 几座干旱区中的城市不可能建有水利设施。

样例输入

2 5
9 1 5 4 3
8 7 6 1 2

样例输出

1
1

提示

【样例说明】只需要在海拔为9的那座城市中建造蓄水厂,即可满足要求。

在这里插入图片描述

C语言实现:

#include <stdio.h>
#include <string.h>// 定义二维数组的最大维度,可根据实际需求调整
#define MAX_SIZE 520// 存储地形高度信息的二维数组
int h[MAX_SIZE][MAX_SIZE];
// 用于标记每个位置是否已被访问的二维数组
int vis[MAX_SIZE][MAX_SIZE];
// 记录从每个位置出发能到达的最左列索引的二维数组
int l[MAX_SIZE][MAX_SIZE];
// 记录从每个位置出发能到达的最右列索引的二维数组
int r[MAX_SIZE][MAX_SIZE];
// 定义四个方向的偏移量,用于在二维数组中移动
int fx[4][2] = { {0, -1}, {-1, 0}, {1, 0}, {0, 1} };
// 用于计数的变量,根据不同情况有不同用途
int cnt;
// 存储二维数组的行数和列数
int n, m;
// 标记是否能从第一行到达最后一行所有位置的标志变量
int flag = 1;// 深度优先搜索函数,用于遍历二维数组
void dfs(int x, int y) {vis[x][y] = 1; // 标记当前位置 (x, y) 已被访问int xx, yy;// 遍历四个方向for (int i = 0; i < 4; i++) {xx = x + fx[i][0];yy = y + fx[i][1];// 判断新位置是否在合法范围内if (xx < 1 || yy < 1 || xx > n || yy > m) continue;// 如果当前位置的高度小于等于新位置的高度,跳过if (h[x][y] <= h[xx][yy]) continue;// 如果新位置未被访问,则递归调用dfs继续探索if (!vis[xx][yy]) dfs(xx, yy);// 更新当前位置能到达的最左列索引l[x][y] = l[x][y] < l[xx][yy]? l[x][y] : l[xx][yy];// 更新当前位置能到达的最右列索引r[x][y] = r[x][y] > r[xx][yy]? r[x][y] : r[xx][yy];}
}int main() {// 读取二维数组的行数和列数scanf("%d %d", &n, &m);// 初始化l数组为较大的值,这里使用0x3f作为较大值的表示memset(l, 0x3f, sizeof(l));// 初始化最后一行的最左列索引和最右列索引为对应的列号for (int i = 1; i <= m; i++) {l[n][i] = r[n][i] = i;}// 读取二维数组中的地形高度信息for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {scanf("%d", &h[i][j]);}}// 从第一行的每个位置开始进行深度优先搜索for (int i = 1; i <= m; i++) {if (!vis[1][i]) dfs(1, i);}// 检查最后一行的每个位置是否都被访问到for (int i = 1; i <= m; i++) {if (!vis[n][i]) {flag = 0;cnt++;}}// 如果最后一行存在未被访问到的位置if (flag == 0) {printf("0\n%d", cnt);return 0;}// 用于逐步扩展覆盖范围的变量,表示当前覆盖范围的最左列int left = 1;while (left <= m) {int maxr = 0;// 遍历第一行的每个位置for (int i = 1; i <= m; i++) {if (l[1][i] <= left) {maxr = maxr > r[1][i]? maxr : r[1][i];}}cnt++;left = maxr + 1;}printf("1\n%d", cnt);return 0;
}

在这里插入图片描述


💐The End💐点点关注,收藏不迷路💐

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

鸿蒙开发:arkts 如何读取json数据

为了支持ArkTS语言的开发&#xff0c;华为提供了完善的工具链&#xff0c;包括代码编辑器、编译器、调试器、测试工具等。开发者可以使用这些工具进行ArkTS应用的开发、调试和测试。同时&#xff0c;华为还提供了DevEco Studio这一一站式的开发平台&#xff0c;为运行在Harmony…

OpenCV视觉分析之目标跟踪(11)计算两个图像之间的最佳变换矩阵函数findTransformECC的使用

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 根据 ECC 标准 78找到两幅图像之间的几何变换&#xff08;warp&#xff09;。 该函数根据 ECC 标准 ([78]) 估计最优变换&#xff08;warpMatri…

【2024最新版Kotlin教程】Kotlin第一行代码系列第五课-类继承,抽象类,接口

【2024最新版Kotlin教程】Kotlin第一行代码系列第五课-类继承&#xff0c;抽象类&#xff0c;接口 为什么要有继承呢&#xff0c;现实中也是有继承的&#xff0c;对吧&#xff0c;你继承你爸的遗产&#xff0c;比如你爸建好了一个房子&#xff0c;儿子继承爸&#xff0c;就得了…

iOS用rime且导入自制输入方案

iPhone 16 的 cantonese 只能打传统汉字&#xff0c;没有繁简转换&#xff0c;m d sh d。考虑用「仓」输入法 [1] 使用 Rime 打字&#xff0c;且希望导入自制方案 [2]。 仓输入法有几种导入方案的方法&#xff0c;见 [3]&#xff0c;此处记录 wifi 上传法。准备工作&#xff1…

基于Zynq FPGA的雷龙SD NAND存储芯片性能测试

文章目录 前言一、SD NAND特征1.1 SD卡简介1.2 SD卡Block图 二、SD卡样片三、Zynq测试平台搭建3.1 测试流程3.2 SOC搭建 四、软件搭建五、测试结果六、总结 前言 随着嵌入式系统和物联网设备的快速发展&#xff0c;高效可靠的存储解决方案变得越来越重要。雷龙发展推出的SD NA…

【动态规划 数学】2745. 构造最长的新字符串|1607

本文涉及知识点 C动态规划 数学 LeetCode2745. 构造最长的新字符串 给你三个整数 x &#xff0c;y 和 z 。 这三个整数表示你有 x 个 “AA” 字符串&#xff0c;y 个 “BB” 字符串&#xff0c;和 z 个 “AB” 字符串。你需要选择这些字符串中的部分字符串&#xff08;可以全…

【Linux驱动开发】timer库下的jiffies时间戳和延时驱动编写

【Linux驱动开发】timer库下的jiffies时间戳和延时驱动编写 gitee地址&#xff1a; https://gitee.com/Mike_Zhou_Admin/Linux_Driver_Timestamp_Driver/更新以gitee为准 文章目录 timer库时间戳函数延时函数驱动代码应用测试附录&#xff1a;嵌入式Linux驱动开发基本步骤开发…

了解云计算工作负载保护的重要性及必要性

云计算de小白 云计算技术的快速发展使数据和应用程序安全成为一种关键需求&#xff0c;而不仅仅是一种偏好。随着越来越多的客户公司将业务迁移到云端&#xff0c;保护他们的云工作负载&#xff08;指所有部署的应用程序和服务&#xff09;变得越来越重要。云工作负载保护&…

C语言 循环高级

时间&#xff1a;2024.11.6 一、学习内容 1、无限循环 无限循环&#xff1a;循环永远停不下来 注意点&#xff1a;无限循环因为永远停不下来&#xff0c;所以下面不能再写其他的代码了 2、break 跳转控制语句&#xff1a; 在循环的过程中&#xff0c;跳到其他语句上执行 #…

易语言模拟真人动态生成鼠标滑动路径

一.简介 鼠标轨迹算法是一种模拟人类鼠标操作的程序&#xff0c;它能够模拟出自然而真实的鼠标移动路径。 鼠标轨迹算法的底层实现采用C/C语言&#xff0c;原因在于C/C提供了高性能的执行能力和直接访问操作系统底层资源的能力。 鼠标轨迹算法具有以下优势&#xff1a; 模拟…

CSS学习之Grid网格布局基本概念、容器属性

网格布局 网格布局&#xff08;Grid&#xff09;是将网页划分成一个个网格单元&#xff0c;可任意组合不同的网格&#xff0c;轻松实现各种布局效果&#xff0c;也是目前CSS中最强大布局方案&#xff0c;比Flex更强大。 基本概念 容器和项目 当一个 HTML 元素将 display 属性…

聊一聊Elasticsearch的索引的分片分配机制

1、什么是分片分配 分片分配是由ES主节点将索引分片移动到ES集群中各个节点上的过程。 该过程尽量保证&#xff0c;同一个索引的分片尽量分配到更多的节点上&#xff0c;以此来达到读写索引的时候可以利用更多硬件资源的效果。 在分配过程当中&#xff0c;也不能将某个主分片…

springboot的增删改查商城小实践(b to c)

首先准备一张表&#xff0c;根据业务去设计表 订单编号是参与业务的&#xff0c;他那订单编号里面是有特殊意义的&#xff0c;比如说像什么一些年月日什么的&#xff0c;一些用户的ID都在那编号里面呢&#xff1f;不能拿这种东西当主件啊 根据数据量去决定数据类型 价格需要注意…

Ubuntu 安装 RTL8811cu 网卡驱动

一、支持的网卡 RTL8811AU、RTL8811CU、RTL8821AU、RTL8821CU 二、下载驱动 github&#xff1a;https://github.com/brektrou/rtl8821CU 直接下载zip源码即可 三、安装驱动 sudo su -i #切换到root用户 apt-get update #更新安装源 apt-get install -y dkms …

解锁炎症和肿瘤免疫治疗新靶点:TREM1&TREM2

前 言 TREM家族属于细胞表面受体&#xff0c;介导调控炎症反应&#xff0c;现已成为癌症、神经退行性疾病以及炎症性疾病等多种疾病最有潜力的药物靶点。截至2023年6月&#xff0c;有5项FDA注册的临床前或临床试验正在进行中&#xff0c;有3项是TREM2在阿尔茨海默症&#xff…

【Unity】Unity拖拽在Android设备有延迟和卡顿问题的解决

一、介绍 在制作Block类游戏时&#xff0c;其核心的逻辑就是拖拽方块放入到地图中&#xff0c;这里最先想到的就是Unity的拖拽接口IDragHandler,然后通过 IPointerDownHandler, IPointerUpHandler 这两个接口判断按下和松手&#xff0c;具体的实现逻辑就是下面 public void On…

Postman断言与依赖接口测试详解!

在接口测试中&#xff0c;断言是不可或缺的一环。它不仅能够自动判断业务逻辑的正确性&#xff0c;还能确保接口的实际功能实现符合预期。Postman作为一款强大的接口测试工具&#xff0c;不仅支持发送HTTP请求和接收响应&#xff0c;还提供了丰富的断言功能&#xff0c;帮助测试…

NewStar CTF 2024 misc WP

decompress 压缩包套娃&#xff0c;一直解到最后一层&#xff0c;将文件提取出来 提示给出了一个正则&#xff0c;按照正则爆破密码&#xff0c;一共五位&#xff0c;第四位是数字 ^([a-z]){3}\d[a-z]$ 一共就五位数&#xff0c;直接ARCHPR爆破&#xff0c;得到密码 xtr4m&…

鸿蒙开发案例:七巧板

【1】引言&#xff08;完整代码在最后面&#xff09; 本文介绍的拖动七巧板游戏是一个简单的益智游戏&#xff0c;用户可以通过拖动和旋转不同形状的七巧板块来完成拼图任务。整个游戏使用鸿蒙Next框架开发&#xff0c;利用其强大的UI构建能力和数据响应机制&#xff0c;实现了…

C++_STL_xx_番外01_关于STL的总结(常见容器的总结;关联式容器分类及特点;二叉树、二叉搜索树、AVL树(平衡二叉搜索树)、B树、红黑树)

文章目录 1. 常用容器总结2. 关联式容器分类3. 二叉树、二叉搜索树、AVL树、B树、红黑树 1. 常用容器总结 针对常用容器的一些总结&#xff1a; 2. 关联式容器分类 关联式容器分为两大类&#xff1a; 基于红黑树的set和map&#xff1b;基于hash表的unorder_set和unorder_ma…