tzoj:3613 突破包围
2024-10-21 15:57:38
http://www.tzcoder.cn/acmhome/problemdetail.do?&method=showdetail&id=3613
算出两两之间min距离,然后从起点开始循环时间点,到的了的地方进队
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define pai pair<int,int>
char mp[105][105];
struct node{
int x,y,ii;
}e,s;
int m,n,k;
vector<node>ve;
vector<pai>v[100105];
int visit[105][105],stp[105][105],kk[105];
int xi[]={1,-1,0,0};
int yi[]={0,0,1,-1};
int solve(node a,node b)//算出两点间最短距离
{
memset(visit,0,sizeof visit);
visit[a.x][a.y]=1;
memset(stp,INF,sizeof stp);
stp[a.x][a.y]=0;
queue<node>qu;
qu.push(a);
while(!qu.empty()){
node q=qu.front();qu.pop();
if(q.x==b.x&&q.y==b.y)return stp[q.x][q.y];
for(int i=0;i<4;i++){
int xx=xi[i]+q.x,yy=yi[i]+q.y;
if(xx>=0&&xx<n&&yy>=0&&yy<m&&visit[xx][yy]==0&&mp[xx][yy]!='x'){
visit[xx][yy]=1;
node p;p.x=xx,p.y=yy;
stp[p.x][p.y]=stp[q.x][q.y]+1;
qu.push(p);
}
}
}
return INF;
}
int solve2(node a,node b)//按时间点进队,看是否能走到终点
{
int i,j;
memset(visit,0,sizeof visit);
visit[a.x][a.y]=1;
queue<node>qu;
a.ii=0;//这里注意先赋值再进队!!这点wa了
qu.push(a);
i=1;
while(!qu.empty()){
while(!qu.empty()&&qu.front().ii+1==i){
node p=qu.front();qu.pop();
if(p.x==b.x&&p.y==b.y)return 1;
for(j=0;j<v[p.x*1000+p.y].size();j++){
int xi=v[p.x*1000+p.y][j].first,yi=v[p.x*1000+p.y][j].second;
int xx=xi/1000,xy=xi%1000;
if(yi<=kk[i]&&visit[xx][xy]==0){
visit[xx][xy]=1;
node op;op.x=xx,op.y=xy,op.ii=p.ii+1;
if(op.x==b.x&&op.y==b.y)return 1;
qu.push(op);
}
}
p.ii++;
qu.push(p);
}//一个时间点循环一段
i++;
if(i>k)return 0;
}
return 0;
}
int main()
{
int i,j,t;scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&m);
ve.clear();
for(i=0;i<n;i++){
scanf("%s",mp[i]);
for(j=0;j<m;j++){
if(mp[i][j]=='y')s.x=i,s.y=j,ve.push_back(s);
if(mp[i][j]=='d')e.x=i,e.y=j,ve.push_back(e);
if(mp[i][j]=='*'){
node oo;oo.x=i,oo.y=j;ve.push_back(oo);
}
}
}
scanf("%d",&k);
for(i=1;i<=k;i++)scanf("%d",&kk[i]);
for(i=0;i<100105;i++)v[i].clear();//这里不要=100105,!!这也wa了!
for(i=0;i<ve.size();i++){
for(j=i+1;j<ve.size();j++){
int dis=solve(ve[i],ve[j]);
int a=ve[i].x*1000+ve[i].y,b=ve[j].x*1000+ve[j].y;
v[a].push_back(pai(b,dis));
v[b].push_back(pai(a,dis));
}
}
int f=solve2(s,e);
if(f==1)printf("good luck!\n");
else printf("poor yzq!\n");
}
}
最新文章
- 【STL】-Map/Multimap的用法
- jquery UI Draggable和Droppable 案例
- wavecom短信猫常用AT命令
- $(document).ready(function(){});不执行
- Borg Maze poj 3026
- fatal error C1083: Cannot open include file: &#39;qttreepropertybrowser.moc&#39;: No such file or directory
- LIst去重,重写方法,继承接口。
- poj3468(一维)(区间查询,区间修改)
- python20171113笔记
- 集合之LinkedList源码分析
- 深入理解CoordinatorLayout.Behavior
- GCC/gcc/g++/CC/cc区别
- Docker常用镜像
- ubuntu18下安装docker
- mysql字段有中英文,数字按照升序/降序 排序
- 潭州课堂25班:Ph201805201 django 项目 第二十四课 文章主页 多级评论数据库设计 ,后台代码完成 (课堂笔记)
- Windows 系统安装多个版本JDK, 修改环境变量不生效
- 滑动条QSlider
- 瀑布流之ajax
- mysql自动创建分区
热门文章
- ENGG1310 Electricity and electronics P1.2 Electronic Communication
- PK获取面积
- version libcrypto.so.10 not defined in file libcrypto.so.10 with link time reference
- Kubernetes--Pod生命周期中的重要行为
- Java基础学习:6、方法的重载和可变参数
- Visual Studio 安装时,共享组件、工具和SDK的路径无法更改解决方法
- 下载安装sqlyog
- python 安装redis,rediscluster
- 23_webpack_TreeShaking
- vue3 门户网站搭建8-字体