【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💐点点关注,收藏不迷路💐 |
相关文章:
【NOIP提高组】引水入城
【NOIP提高组】引水入城 💐The Begin💐点点关注,收藏不迷路💐 在一个遥远的国度,一侧是风景秀美的湖泊,另一侧则是漫无边际的沙漠。该国的行政 区划十分特殊,刚好构成一个N行M列的矩形ÿ…...
openvino python推理demo
openvino python推理demo import openvino from openvino.runtime import Core import numpy as np import argparse import hashlib import os import ioclass OpenvinoInfer:def __init__(self,device_id0):self.device_iddevice_idself.ie Core()self.available_devices …...
JavaWeb项目-----博客系统
一.设计数据库 1.创建数据库 create database if not exists java108_blog_system character set utf8; drop table if exists user; drop table if exists blog;2.创建博客列表 create table blog(blogId int primary key auto_increment,title varchar(20),content varcha…...
GY-56 (VL53L0X) 激光测距
文章目录 一、GY-56 简介二、引脚功能三、通信协议1.串口协议: 当 GY-56 PS 焊点开放时候使用(默认)(1)串口通信参数(默认波特率值 9600bps)(2)模块输出格式,每帧包含 8-13 个字节&a…...
当今陪玩系统小程序趋势,陪玩系统源码搭建后的适用于哪些平台
一、市场规模持续扩大 随着全球游戏市场的不断膨胀,游戏陪玩行业正逐渐从一个新兴领域成长为游戏产业链中不可或缺的一环。据《2024年1~6月中国游戏产业报告》显示,今年上半年,国内游戏市场实际销售收入达到1472.67亿元,同比增长…...
qt QListWidget详解
1、概述 QListWidget 是 Qt 框架中的一个类,它提供了一个基于模型的视图,用于显示项目的列表。QListWidget 继承自 QAbstractItemView 并为项目列表提供了一个直观的接口。与 QTreeView 和 QTableView 不同,QListWidget 是专门为单行或多行项…...
java ssm 校园快递物流平台 校园快递管理系统 物流管理 源码 jsp
一、项目简介 本项目是一套基于SSM的校园快递物流平台,主要针对计算机相关专业的和需要项目实战练习的Java学习者。 包含:项目源码、数据库脚本、软件工具等。 项目都经过严格调试,确保可以运行! 二、技术实现 后端技术&#x…...
西安电子科技大学考研网报审核通过了,然后呢?
报考西安电子科技大学的宝贝们,考研网上确认已经截止的同学们,不用担心! 最近,有很多同学问到一个问题:网上确认时看到有消息说禁止使用海马体照片,但我明明用了海马体的照片,审核却通过了&…...
pandas习题 051:将字符串数据读取到 DataFrame
编码题)有以下逗号隔开和空格隔开的字符串数据,如何将它读取为 DataFrame ? data = ‘’’ a,b,c 1,3,4 2,4,5 ‘’’ data2 = ‘’’ a b c 1 13 214 2 4 15 ‘’’ Python 代码如下:import pandas as pd import iodata = a,b,c 1,3,4 2,4,5 df = pd.read_csv(io.Stri…...
改进探路者算法复现
本文所涉及所有资源均在 传知代码平台 可获取。 目录 一、背景及意义介绍 (一)背景 ...
PostgreSQL 学习笔记:PostgreSQL 主从复制
PostgreSQL 笔记:PostgreSQL 主从复制 博客地址:TMDOG 的博客 在现代应用程序中,数据库的高可用性和扩展性是至关重要的。PostgreSQL 提供了主从复制功能,可以在多个数据库实例之间复制数据,以实现冗余和负载均衡。本…...
【系统架构设计师(第2版)】十一、未来信息综合技术
未来信息综合技术是指近年来新技术发展而提出的一些新概念、新知识、新产品,主要包括信息物理系统(CPS)、人工智能(AI)、机器人、边缘计算、数字孪生、云计算和大数据等技术。这些技术涉及多学科、多领域,具…...
Pytorch学习--神经网络--优化器
一、头文件 torch.optim.Optimizer(params, defaults) optim文档 for input, target in dataset:optimizer.zero_grad()output model(input)loss loss_fn(output, target)loss.backward()optimizer.step()二、代码 不带优化器的代码框架 import torch import torchvision…...
w~自动驾驶合集11
我自己的原文哦~ https://blog.51cto.com/whaosoft/12329152 #特斯拉的“纯视觉”路线 , 也许不是最好的 BEVTransformer占用网络技术路线的大热,再次将激光雷达推向风口浪尖。 激光雷达该不该被抛弃? 对车企来说,这是一个艰难的抉择&am…...
大数据新视界 -- 大数据大厂之 Impala 性能优化:解锁大数据分析的速度密码(上)(1/30)
💖💖💖亲爱的朋友们,热烈欢迎你们来到 青云交的博客!能与你们在此邂逅,我满心欢喜,深感无比荣幸。在这个瞬息万变的时代,我们每个人都在苦苦追寻一处能让心灵安然栖息的港湾。而 我的…...
GESP4级考试语法知识(算法概论(三))
爱因斯坦的阶梯代码: //算法1-12 #include<iostream> using namespace std; int main() {int n1; //n为所设的阶梯数while(!((n%21)&&(n%32)&&(n%54)&&(n%65)&&(n%70)))n; //判别是否满足一组同余式cout<<n<…...
x-cmd pkg | gum - 轻松构建美观实用的终端界面,解锁命令行新玩法
目录 简介快速上手安装使用 功能特点竞品和相关作品进一步探索 简介 gum 是由 Charm 团队于 2022 年使用 Go 开发的终端 UI 组件工具箱,能帮用户在终端中快速构建交互式 TUI 界面(如表单、菜单、提示框等),简化命令行应用程序的开…...
WMS系统打通仓储全链条数据势在必行,该如何做呢
一、引言 在当今竞争激烈的商业环境中,高效的仓储管理对于企业的生存和发展至关重要。仓储管理系统(WMS)作为现代仓储管理的核心工具,其作用不仅仅是简单地记录库存数量和位置,更在于打通仓储全链条数据,实…...
基于Python的校园爱心帮扶管理系统
作者:计算机学姐 开发技术:SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等,“文末源码”。 专栏推荐:前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏:…...
如何基于pdf2image实现pdf批量转换为图片
最近为了将pdf报告解析成为文本和图片,需要将大量多页的pdf文件拆分下单独的一页一页的图像,以便后续进行OCR和图像处理,因此就需要实现将pdf2image,本文主要结合开源的pdf2image和poppler,实现了pdf转换为png格式图片…...
会议纪要助手:OpenClaw+nanobot自动提炼讨论要点
会议纪要助手:OpenClawnanobot自动提炼讨论要点 1. 为什么需要自动化会议纪要 每次开完会最头疼的就是整理会议纪要。作为技术负责人,我每周要参加至少5场会议,从需求评审到技术方案讨论,经常一开就是两小时。会后花半小时手动整…...
neural-style-tf视频风格转换实战:让整个视频充满艺术气息
neural-style-tf视频风格转换实战:让整个视频充满艺术气息 【免费下载链接】neural-style-tf TensorFlow (Python API) implementation of Neural Style 项目地址: https://gitcode.com/gh_mirrors/ne/neural-style-tf neural-style-tf是一个基于TensorFlow实…...
[带AI]基于SpringBoot+Vue的青少年心理健康管理系统设计与实现+文档+指导搭建视频
|前后端分离|Java|SpringBoot|Vue3|Spring AI智能对话一、项目技术栈项目采用技术:① 架构模式:前后端分离开发② 系统环境:Windows、Mac③ 开发环境:IDEA、JDK21、MySQL…...
嵌入式开发硬件知识体系与核心技能解析
嵌入式开发中的硬件知识体系构建1. 嵌入式开发的技术架构1.1 嵌入式系统技术分类现代嵌入式系统开发主要分为两大技术方向:嵌入式硬件开发:聚焦电路原理设计、PCB布局及硬件系统集成嵌入式软件开发:包含驱动层开发和应用程序开发两个层级1.2 …...
解锁Stable Diffusion隐藏玩法:用ChatGPT批量生成动漫角色Prompt全攻略
从零到大师:ChatGPT与Stable Diffusion打造专属动漫角色的终极指南 在数字艺术创作领域,AI绘画工具正掀起一场前所未有的革命。想象一下,你脑海中那个独特的动漫角色形象,不再需要数月的美术训练就能实现——只需要正确的工具组合…...
Bili2Text:B站视频转文字的智能革命
Bili2Text:B站视频转文字的智能革命 【免费下载链接】bili2text Bilibili视频转文字,一步到位,输入链接即可使用 项目地址: https://gitcode.com/gh_mirrors/bi/bili2text 副标题:还在为视频笔记熬夜?这款工具让…...
基于MATLAB的图像加密解密系统 可以正确无误的对图像进行加密和解密 带GUI界面
基于MATLAB的图像加密解密系统 可以正确无误的对图像进行加密和解密 带GUI界面,一步一步完整运行你是否有过这样的疑问——如何让一张普通图片变成外星密文?在MATLAB里玩转图像加密真的可以像搭积木一样简单。今天咱们就来捣鼓一个带界面的图像加密系统&…...
Kronos时间序列预测模型全攻略:从技术原理到工业实践
Kronos时间序列预测模型全攻略:从技术原理到工业实践 【免费下载链接】Kronos Kronos: A Foundation Model for the Language of Financial Markets 项目地址: https://gitcode.com/GitHub_Trending/kronos14/Kronos 问题:时间序列预测的行业痛点…...
MySQL误删数据别慌!手把手教你用binlog2sql从ROW格式日志恢复(附常见报错解决方案)
MySQL数据恢复实战:从误删到完美还原的完整指南 凌晨三点,当大多数人都沉浸在梦乡时,数据库管理员小李却被一阵急促的电话铃声惊醒。生产环境的核心用户表被误操作清空,数百万条用户数据瞬间消失。这种场景对于任何DBA来说都是噩梦…...
Mplus路径系数差异比较实战:两种方法详解与选择指南
Mplus路径系数差异比较实战:两种方法详解与选择指南 在结构方程模型分析中,研究者常常需要比较不同路径系数或中介效应是否存在显著差异。比如,你可能想知道性别对工作满意度的直接影响是否显著大于其对组织承诺的影响,或者比较两…...
