【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格式图片…...

未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...

stm32G473的flash模式是单bank还是双bank?
今天突然有人stm32G473的flash模式是单bank还是双bank?由于时间太久,我真忘记了。搜搜发现,还真有人和我一样。见下面的链接:https://shequ.stmicroelectronics.cn/forum.php?modviewthread&tid644563 根据STM32G4系列参考手…...

【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...
CSS | transition 和 transform的用处和区别
省流总结: transform用于变换/变形,transition是动画控制器 transform 用来对元素进行变形,常见的操作如下,它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障
关键领域软件测试的"安全密码":Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力,从金融交易到交通管控,这些关乎国计民生的关键领域…...