P1902 刺杀大使
2024-09-22 15:05:14
题目描述
伊朗伊斯兰革命卫队(某恐怖组织)正在策划一起刺杀行动,他们的目标是沙特驻美大 使朱拜尔。他们来到了沙特驻美使馆,准备完成此次刺杀,要进入使馆首先必须通过使馆前 的防御迷阵。
迷阵由 n*m 个相同的小房间组成,每个房间与相邻四个房间之间有门可通行。在第 n 行的 m 个房间里有 m 个机关,这些机关必须全部打开才可以进入大使馆。而第 1 行的 m 个 房间有 m 扇向外打开的门,是迷阵的入口。除了第 1 行和第 n 行的房间外,每个房间都被 使馆的安保人员安装了激光杀伤装置,将会对进入房间的人造成一定的伤害。第 i 行第 j 列 造成的伤害值为 p[i][j](第 1 行和第 n 行的 p 值全部为 0)。
现在伊斯兰革命卫队打算以最小伤害代价进入迷阵,打开全部机关,显然,他们可以选 择任意多的人从任意的门进入,但必须到达第 n 行的每个房间。一个士兵受到的伤害值为他 到达某个机关的路径上所有房间的伤害值中的最大值,整个部队受到的伤害值为所有士兵的 伤害值中的最大值。现在,这个恐怖组织掌握了迷阵的情况,他们需要提前知道怎么安排士 兵的行进路线可以使得整个部队的伤害值最小。
输入输出格式
输入格式:
第一行有两个整数 n,m,表示迷阵的大小。
接下来 n 行,每行 m 个数,第 i 行第 j 列的数表示 p[i][j]。
输出格式:
输出一个数,表示最小伤害代价。
输入输出样例
说明
50%的数据,n,m<=100;
100%的数据,n,m<=1000,p[i][j]<=1000。
//因为最后一行都是0,所以只要可以到达最后一行的任意一点,整个最后一行就可以打开
//找到一个人的最小伤害之后,整个军队就可以沿着这个人的路径过去
//所以就是找一个人能过去的最小伤害
//二分mid,搜索判断是否可以过去 #include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std; const int N=1e3+; inline int read()
{
char c=getchar();int num=,f=;
for(;!isdigit(c);c=getchar())
f=c=='-'?-:f;
for(;isdigit(c);c=getchar())
num=num*+c-'';
return num*f;
} int n,m;
int injure[N][N]; bool flag;
int vis[N][N],tim;
int cx[]={,,,-},cy[]={,,-,};
void dfs(int x,int y,int mid)
{
if(x==n)
{
flag=;
return;
}
vis[x][y]=tim;
for(int i=,xx,yy;i<;++i)
{
xx=x+cx[i],yy=y+cy[i];
if(xx<||xx>n||yy<||yy>m||vis[xx][yy]==tim||injure[xx][yy]>mid)
continue;
dfs(xx,yy,mid);
if(flag)
return;
}
} int main()
{
n=read(),m=read();
for(int i=;i<=n;++i)
for(int j=;j<=m;++j)
injure[i][j]=read();
int l=,r=,mid,ans=;
while(l<=r)
{
mid=l+r>>;
++tim;
flag=;
dfs(,,mid);
if(flag)
{
ans=mid;
r=mid-;
}
else
l=mid+;
}
printf("%d",ans);
return ;
}
最新文章
- win7挂载VHD文件,模拟多系统并存
- 简单的java socket 示例
- Android高性能ORM数据库DBFlow入门
- Apache MPM winnt
- git push 提示
- pod 命令-bash: --: command not found
- DDD的ABP开发框架
- Web 项目更改项目名
- MongoDB的CURD命令
- 一步步建立 Vue + Cesium 初始化项目
- 2018-2019-2 《网络对抗技术》Exp0 Kali安装 Week1 20165316
- JavaScript对象(第四天)
- 【4opencv】识别复杂的答题卡1(主要算法)
- springMVC的执行流程和完整代码
- 常量表达式和constexpr(c++11)
- 分类器评估方法:精确度-召回率-F度量(precision-recall-F_measures)
- 接口开发-基于SpringBoot创建基础框架
- 可视化iOS应用程序开发的6个Xcode小技巧
- Objective-C:用命令行参数的格式对文件进行IO操作
- C#基础-获得当前程序的 空间名.类名.方法名