《算法竞赛·快冲300题》每日一题:“造电梯”
《算法竞赛·快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。
所有题目放在自建的OJ New Online Judge。
用C/C++、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。
文章目录
- 题目描述
- 题解
- C++代码
- Java代码
- Python代码
“ 造电梯” ,链接: http://oj.ecustacm.cn/problem.php?id=1790
题目描述
【题目描述】 现在给你一张建筑的平面图,按照要求,建筑的每一个部分都应该是轮椅使用者可以到达的,这意味着必须安装电梯。
给定的平面图是一个n*m的矩阵,里面的数字表示这个位置的高度。可以在建筑中的任意位置放置电梯,电梯可以停在所有楼层。
需要保证可以使用电梯到达所有高楼层。相同高度的楼层之间是互通的,联通准则是四联通。
需要求解最少需要多少个电梯,注意高度为1的不需要电梯。
下图展示了样例2的可视化三维图。

【输入格式】 输入第一行为n和m(1≤n,m≤500)。
接下来n行,每行m个整数xij,表示平面图,0≤xij≤10^9。
【输出格式】 输出最少电梯数量
【输入样例】
样例1:
2 3
1 2 3
1 3 2样例2:
6 7
0 0 0 0 0 0 0
0 1 2 3 2 1 0
0 1 2 3 2 1 0
0 0 0 0 0 0 0
0 1 0 5 0 0 0
0 0 0 0 0 0 0
【输出样例】
样例1:
2样例2:
2
题解
电梯是装在建筑内部的,例如样例2,高度5的柱子内部需要一个电梯,楼梯状的建筑也需要一个电梯。
注意一个建筑内部可能需要不止一个电梯,例如平面上一个建筑的高度是{5, 2, 4},那么需要在5和4上建2个电梯。
本题是“洪水填充(《算法竞赛》清华大学出版社,罗勇军,郭卫斌著,120页,3.3 洪水填充)”的应用:从最高处开始倒水,那么水会平流或者往下流,这相当于建了一部电梯;这次倒水没有流到的地方,继续从下一个最高处倒水…
以样例2为例:
(1)从最高的“5”开始倒水,水会平流或往下流,那么会继续淹没所有的“0”。这次倒水相当于建设了一部电梯。没有被这次倒水淹没的有第二行和第三行的“1 2 3 2 1”,还有倒数第二行的“1”。
(2)继续从剩下的最高点“3”开始倒水,水会平流或往下流,那么第二行和第三行的“1 2 3 2 1”,还有所有的“0”都会淹没。这次倒水也相当于建设了一部电梯。没有被这次倒水淹没的有倒数第二行的“1”,不过它不需要建设电梯。
“洪水填充”用BFS或DFS都行,下面的代码用BFS实现。把平面的所有点放进优先队列,然后依次取出队列中的最高点,并从它开始“洪水填充”。
【重点】 洪水填充。
C++代码
代码的计算复杂度,设平面上共n个点,每个点只需要处理一次,优先队列进出一次是O(logn)的,所以总复杂度O(nlogn)。
#include <bits/stdc++.h>
using namespace std;
int dx[4] = { 1, 0, -1, 0 }; //上下左右
int dy[4] = { 0, 1, 0, -1 };
struct Point {int x, y, h; //坐标xy、高度hPoint(int x_, int y_, int h_) { x = x_; y = y_; h = h_; };bool operator<(const Point& r) const { return (h < r.h); }
};
int n, m;
int a[505][505];
bool done[505][505]; //done[x][y]=1表示(x,y)已经淹没
void floodfill(int x, int y) { //“洪水填充”,平流或往下流done[x][y] = true; //标记为淹没for (int i = 0; i < 4; i++) { //扩散周围与它等高或矮的点int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= m || ny < 0 || ny >= n || done[nx][ny]) continue;if (a[nx][ny] <= a[x][y])floodfill(nx, ny); //继续“洪水填充”}
}
int main() {cin >> n >> m;priority_queue<Point> Q; //优先队列,队首的h最大for (int j = 0; j < n; j++)for (int i = 0; i < m; i++) {cin >> a[i][j];done[i][j] = (a[i][j] <= 1); //0和1标记为已经淹没if(a[i][j] > 1)Q.push(Point(i, j, a[i][j])); //把点放进优先队列}int ans = 0;while (!Q.empty()) {Point p = Q.top(); //每次取出剩下的最高点Q.pop();if (!done[p.x][p.y]) { //如果它没有淹没过,就“洪水填充”ans++; //这次倒水相当于建设了一部电梯floodfill(p.x, p.y); //“洪水填充”}}cout << ans << endl;return 0;
}
Java代码
import java.util.*;
class Point implements Comparable<Point> {int x, y, h;public Point(int x_, int y_, int h_) {x = x_;y = y_;h = h_;}public int compareTo(Point r) { return Integer.compare(-h, -r.h); }
}public class Main {static int[] dx = { 1, 0, -1, 0 };static int[] dy = { 0, 1, 0, -1 };static int n, m;static int[][] a;static boolean[][] done;public static void floodfill(int x, int y) {done[x][y] = true;for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx < 0 || nx >= m || ny < 0 || ny >= n || done[nx][ny])continue;if (a[nx][ny] <= a[x][y])floodfill(nx, ny);}}public static void floodfill_bfs(int sx, int sy) {Queue<int[]> queue = new LinkedList<>();queue.add(new int[] { sx, sy });done[sx][sy] = true;while (!queue.isEmpty()) {int[] curr = queue.poll();int x = curr[0];int y = curr[1];for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];if (nx >= 0 && nx < m && ny >= 0 && ny < n && !done[nx][ny] && a[nx][ny] <= a[x][y]) {queue.add(new int[] { nx, ny });done[nx][ny] = true;}}}}public static void main(String[] args) {Scanner input = new Scanner(System.in);n = input.nextInt();m = input.nextInt();a = new int[m][n];done = new boolean[m][n];PriorityQueue<Point> Q = new PriorityQueue<>();for (int j = 0; j < n; j++) {for (int i = 0; i < m; i++) {a[i][j] = input.nextInt();done[i][j] = (a[i][j] <= 1);if (a[i][j] > 1) Q.add(new Point(i, j, a[i][j]));}}int ans = 0;while (!Q.isEmpty()) {Point p = Q.poll();if (!done[p.x][p.y]) {ans++;floodfill_bfs(p.x, p.y);}}System.out.println(ans);input.close();}
}
Python代码
from collections import deque
import heapq
import sys
input = sys.stdin.readlinedx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
n, m = map(int, input().split())
a = [[0] * n for _ in range(m)]
done = [[False] * n for _ in range(m)]Q = []
for j in range(n):row_a = list(map(int, input().split()))for i in range(m):a[i][j] = row_a[i]if a[i][j] <= 1: done[i][j]=Trueelse: heapq.heappush(Q, (-a[i][j], i, j))
ans = 0
while Q:_, sx, sy = heapq.heappop(Q)if not done[sx][sy]:ans += 1q = deque([(sx, sy)])done[sx][sy] = True while q:x, y = q.popleft()for i in range(4):nx, ny = x + dx[i], y + dy[i]if 0 <= nx < m and 0 <= ny < n and not done[nx][ny] and a[nx][ny] <= a[x][y]:q.append((nx, ny))done[nx][ny] = True
print(ans)
相关文章:
《算法竞赛·快冲300题》每日一题:“造电梯”
《算法竞赛快冲300题》将于2024年出版,是《算法竞赛》的辅助练习册。 所有题目放在自建的OJ New Online Judge。 用C/C、Java、Python三种语言给出代码,以中低档题为主,适合入门、进阶。 文章目录 题目描述题解C代码Java代码Python代码 “ 造…...
NSS [MoeCTF 2022]baby_file
NSS [MoeCTF 2022]baby_file 题目源码直接给了 使用data伪协议发现被ban了。 那就换一种伪协议php://filter,猜测flag在同目录下flag.php中或根目录下/flag中 php://filter/readconvert.base64-encode/resourceflag.php读取文件源码(针对php文件需要ba…...
喜报!诚恒科技与赛时达科技达成BI金蝶云星空项目合作
随着全球数字化浪潮轰轰烈烈袭来,仅仅凭借手工处理的方式难以在庞大的数据海洋中精准获取信息、把握市场需求、了解目标用户,为企业创新提供强有力的支持。深圳赛时达科技有限公司(简称赛时达科技)希望通过数字化转型实现从手工处…...
Vscode python调试和运行环境设置
Vscode python调试和运行环境设置 文章目录 Vscode python调试和运行环境设置前言一、是否为每次运行python程序都要选择环境烦恼二、是否为python程序调试不能进标准/第三方库而烦恼 前言 一、是否为每次运行python程序都要选择环境烦恼 在.vscode文件夹(没有就自己造一个)下…...
lua中执行luci.sys.call、luci.sys.exec、os.execute的区别
相同点:都是调用Linux底层脚本及程序 不同点: (1)luci.sys.call(command) 脾气捉摸不透,实际使用有些时候没有得到任何状态或数据返回,纯粹被用了一下。 (2)luci.sys.exec(command) …...
Python-OpenCV中的图像处理-模板匹配
Python-OpenCV中的图像处理-模板匹配 模板匹配单对象的模板匹配多对象的模板匹配 模板匹配 使用模板匹配可以在一幅图像中查找目标函数: cv2.matchTemplate(), cv2.minMaxLoc()模板匹配是用来在一副大图中搜寻查找模版图像位置的方法。 OpenCV 为我们提…...
模拟队列(c++题解)
实现一个队列,队列初始为空,支持四种操作: push x – 向队尾插入一个数 xx;pop – 从队头弹出一个数;empty – 判断队列是否为空;query – 查询队头元素。 现在要对队列进行 MM 个操作,其中的…...
Redis_哨兵模式
9. 哨兵模式 9.1 简介 当主库宕机,在从库中选择一个,切换为主库。 问题: 主库是否真正宕机?哪一个从库可以作为主库使用?如何实现将新的主库的信息通过给从库和客户端? 9.2 基本流程 哨兵主要任务: 监控选择主库通知 会有…...
Mysql中如果建立了索引,索引所占的空间随着数据量增长而变大,这样无论写入还是查询,性能都会有所下降,怎么处理?
索引所占空间的增长确实会对MySQL数据库的写入性能和查询性能造成影响,这主要是由于索引数据过多时会导致磁盘I/O操作变得非常频繁,从而使性能下降。为此,可以采取以下几种方式来减缓这种影响: 1. 限制索引的大小:可以…...
MySQL 约束
查看约束 select * from information_schema.table_constraints where table_name要查看的表名按约束的作用范围 列级约束: 将此约束声明在对应字段的后面 表级约束:在表中所有字段都声明完,在所有字段的后面声明的约束,可以声…...
unity实现角色体力功能【体力条+体力计算】
导读:实现功能 1、角色体力计算 2、角色疲劳动画 3、体力条制作、跟随 默认做好角色的idle/run/walk动画、切换和玩家输入,我使用的是新输入系统,动画时单变量混合树,参数Sports。 【每一部分功能根据自己需求观看哦】 1、角色体…...
【深度学习所有损失函数】在 NumPy、TensorFlow 和 PyTorch 中实现(1/2)
一、说明 在本文中,讨论了深度学习中使用的所有常见损失函数,并在NumPy,PyTorch和TensorFlow中实现了它们。 二、内容提要 我们本文所谈的代价函数如下所列: 均方误差 (MSE) 损失二进制交叉熵损失加权二进…...
七夕好物分享,哪些礼物适合送男/女朋友?这几款好物最为合适!
七夕是个值得纪念的日子,牛郎织女鹊桥相会的故事百年流传,七夕是一个表达爱意的节日,送礼物是必不可少的,情侣们可以选择一份有意义的礼物,也可以选择对方需要的东西当做礼物来赠送,总的来说,送…...
C语言学习系列-->看淡指针(2)
文章目录 前言一、数组名的理解二、使用指针访问数组三、一维数组传参本质四、二级指针五、指针数组六、指针数组模拟二维数组 前言 不把指针学的扎实,可不敢说自己C语言基础学的好 一、数组名的理解 #include <stdio.h> int main() {int arr[10] { 1,2,3,4…...
Java基础篇--Character 类
Character 类是用来操作单个字符的,它将 char 值包装在一个对象中。 实际上,在 Java 中,char 是基本数据类型,而 Character 是 char 的包装类。通过 Character 类,可以使用一系列方法来操作字符。在创建 Character 对…...
Flutter参考资料
Flutter 官网 : https://flutter.dev/ Flutter 插件下载地址 : https://pub.dev/packages Flutter 开发文档 : https://flutter.cn/docs ( 强烈推荐 ) 官方 GitHub 地址 : https://github.com/flutter Flutter 中文社区 : https://flutter.cn/ Flutter 实用教程 : https://flut…...
sed命令如何正确修改ini配置文件
需要保证key值的唯一性 function sed_key_value_file(){key$(echo "$1" | sed s/[\/&]/\\&/g)value$(echo "$2" | sed s/[\/&]/\\&/g)# 先删除原有的value,然后添加新的keyvaluesed -i -e "s#${key}.*#${key}${value}#&q…...
【新版系统架构补充】-信息系统基础知识
信息系统 信息系统的5个基本功能:输入、存储、处理、输出和控制 信息系统的分类(低级到高级):业务(数据)处理系统(TPS/DPS)、管理信息系统(MIS)、决策支持系…...
安防监控视频汇聚平台EasyCVR分发的FLV视频流在VLC中无法播放是什么原因?
众所周知,TSINGSEE青犀视频汇聚平台EasyCVR可支持多协议方式接入,包括主流标准协议国标GB28181、RTSP/Onvif、RTMP等,以及厂家私有协议与SDK接入,包括海康Ehome、海大宇等设备的SDK等。在视频流的处理与分发上,视频监控…...
前端遇到的面试题
1.水平垂直居中 绝对定位 transform position:absolute; top:50%; left:50%; transform:translate(-50%,-50%);绝对定位 margin(子元素宽高知道的情况下) position:absolute; top:50%; left:50%; margin-top:-100px; margin-left:-100px;绝对定位 margin:auto position:a…...
【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...
微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
Vite中定义@软链接
在webpack中可以直接通过符号表示src路径,但是vite中默认不可以。 如何实现: vite中提供了resolve.alias:通过别名在指向一个具体的路径 在vite.config.js中 import { join } from pathexport default defineConfig({plugins: [vue()],//…...
协议转换利器,profinet转ethercat网关的两大派系,各有千秋
随着工业以太网的发展,其高效、便捷、协议开放、易于冗余等诸多优点,被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口,具有实时性、开放性,使用TCP/IP和IT标准,符合基于工业以太网的…...
【UE5 C++】通过文件对话框获取选择文件的路径
目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 ,这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器,右键点击 .uproject 文件,选择 "Generate Visual Studio project files",重…...
加密通信 + 行为分析:运营商行业安全防御体系重构
在数字经济蓬勃发展的时代,运营商作为信息通信网络的核心枢纽,承载着海量用户数据与关键业务传输,其安全防御体系的可靠性直接关乎国家安全、社会稳定与企业发展。随着网络攻击手段的不断升级,传统安全防护体系逐渐暴露出局限性&a…...
