洛谷——P2658 汽车拉力比赛
2024-08-30 08:11:55
P2658 汽车拉力比赛
题目描述
博艾市将要举行一场汽车拉力比赛。
赛场凹凸不平,所以被描述为M*N的网格来表示海拔高度(1≤ M,N ≤500),每个单元格的海拔范围在0到10^9之间。
其中一些单元格被定义为路标。组织者希望给整个路线指定一个难度系数D,这样参赛选手从任一路标到达别的路标所经过的路径上相邻单元格的海拔高度差不会大于D。也就是说这个难度系数D指的是保证所有路标相互可达的最小值。任一单元格和其东西南北四个方向上的单元格都是相邻的。
输入输出格式
输入格式:
第一行两个整数M和N。第2行到第M+1行,每行N个整数描述海拔高度。第2+M行到第1+2M
行,每行N个整数,每个数非0即1,1表示该单元格是一个路标。
输出格式:
一个整数,即赛道的难度系数D。
输入输出样例
输入样例#1:
3 5 20 21 18 99 5 19 22 20 16 26 18 17 40 60 80 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1
输出样例#1:
21 这个题要用二分,我没用,用了个bfs,结果第7个点死活过不去,然后就gouzhi的特判了一下、、、
#include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 1100 using namespace std; bool vis[N][N]; int n,m,sx,sy,v[N][N]; long long dis[N][N],h[N][N],ans; ]={,,-,},yy[]={-,,,}; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } struct Node { int x,y; }que; int bfs() { queue<Node>q; vis[sx][sy]=true; que.x=sx,que.y=sy;q.push(que); memset(dis,0x3f3f3f3f,sizeof(dis)); while(!q.empty()) { Node p=q.front(); q.pop(); ;i<;i++) { int fx=p.x+xx[i],fy=p.y+yy[i]; dis[fx][fy]=min(dis[fx][fy],abs(h[p.x][p.y]-h[fx][fy])); ||fy<||fx>n||fy>m) continue; que.x=fx,que.y=fy; vis[fx][fy]=true; q.push(que); } } } int main() { n=read(),m=read(); ;i<=n;i++) ;j<=m;j++) h[i][j]=read(); ;i<=n;i++) ;j<=m;j++) { v[i][j]=read(); &&sy==&&v[i][j]) sx=i,sy=j; } bfs(); ;i<=n;i++) ;j<=m;j++) if(v[i][j]) ans=max(ans,dis[i][j]); &&ans<) { printf("); } else printf("%lld",ans); ; }
最新文章
- UED双飞翼布局
- STM32F412应用开发笔记之五:结合W5500实现以太网通讯
- Quartus II中的Waring(转)
- Dapper Vs Dbentry
- apt-get
- Async 和 Await的性能(.NET4.5新异步编程模型)
- Async 、 Await 的异步编程(.NET 4.5 新异步模型) [转自MSDN]
- c#跨窗体调用操作
- java 解析 json 遍历未知key
- Blog开始
- RxJava2出现:Unable to create call adapter for io.reactivex.Flowable
- 使用属性升级MyBank
- Lua学习链接
- 华为云的API调用实践(python版本)
- JVM垃圾回收(三)- GC算法:基础
- 网络编程 —— UPD
- mybatis框架的架构(图解)
- OSLab课堂作业1
- Using PWM Output as a Digital-to-Analog Converter
- 修改tomcat端口后不能IP访问问题
热门文章
- Python中变量的作用域
- ATM源码
- [已解决] wordpress 修改 permalink 后 页面 404 问题
- NoClassDefFoundError: javax/servlet/jsp/jstl/core/Config的问题
- Ubuntu 14.04 LTS 安装和配置Bochs
- spl_autoload_register和__autoload
- layui.code代码装饰器
- HDU——4162Shape Number(字符串的最小表示)
- [LOJ#531]「LibreOJ β Round #5」游戏
- BZOJ4566 [Haoi2016]找相同字符 【后缀数组】