Nightmare Ⅱ[HDOJ3085]

题面描述

见HDOJ

思路

本文有$N\ast M$的地图,字符$X$表示墙，$.$表示路，$1$个$boy$，位置在$M$,$1$个$girl$，位置在$G$，$2$个$ghost$,位置在$Z$，$boy$每秒可以在道路上移动三个单位距离，$girl$在道路上移动一个单位距离，每个$ghost$占据的区域每秒可以向四周扩张$2$个单位距离，且无视墙的阻挡，也就是在第$k$秒后所有与鬼的曼哈顿距离不超过$2\ast k$的位置都会被鬼占领.
求在不进入鬼的占领区的前提下，男孩与女孩能否会合，若能会合求出最短会合时间。
$1\le N,M\le 800$
其实观察题面
$boy$每秒可以在道路上移动三个单位距离，$girl$在道路上移动一个单位距离
我们就可以定义bfs的状态:
也就是男孩$bfs3$次，女孩$bfs1$次。再加判断判定此状态时候合法，要实时更新与鬼的曼哈顿距离，即可。

代码

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=810;
const int dx[4]={0,0,-1,1};
const int dy[4]={-1,1,0,0};
struct node
{int x,y;node(){}node(int x,int y):x(x),y(y){}
};
char s[N][N];bool v1[N][N],v2[N][N];
int n,m,px,py,qy,qx;
inline int myabs(int x){return x<0?-x:x;}
bool pd(int x,int y,int k)
{if(x<=0||x>n||y<=0||y>m)return false;if(s[x][y]=='X')return false;if(myabs(x-px)+myabs(y-py)<=2*k)return false;if(myabs(x-qx)+myabs(y-qy)<=2*k)return false;return true;
}void bfs()
{for(int i=1;i<=n;i++)scanf("%s",s[i]+1);int bx,by,gx,gy;px=py=qx=qy=0;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){if(s[i][j]=='M')bx=i,by=j;if(s[i][j]=='G')gx=i,gy=j;if(s[i][j]=='Z'){if(!px&&!py)px=i,py=j;else qx=i,qy=j;}}memset(v1,false,sizeof(v1));memset(v2,false,sizeof(v2));queue<node>q1,q2;int ans=0;q1.push(node(bx,by)),q2.push(node(gx,gy));while(!q1.empty()||!q2.empty()){ans++;for(int t=1;t<=3;t++){int len=q1.size();for(int k=1;k<=len;k++){node t=q1.front();q1.pop();if(!pd(t.x,t.y,ans))continue;for(int i=0;i<4;i++){node nxt=t;nxt.x+=dx[i];nxt.y+=dy[i];if(!pd(nxt.x,nxt.y,ans)||v1[nxt.x][nxt.y])continue;v1[nxt.x][nxt.y]=true;q1.push(nxt);}}}int len=q2.size();for(int k=1;k<=len;k++){node t=q2.front();q2.pop();if(!pd(t.x,t.y,ans))continue;for(int i=0;i<4;i++){node nxt=t;nxt.x+=dx[i];nxt.y+=dy[i];if(!pd(nxt.x,nxt.y,ans)||v2[nxt.x][nxt.y])continue;if(v1[nxt.x][nxt.y]){printf("%d\n",ans);return ;}v2[nxt.x][nxt.y]=true;q2.push(nxt);}}}puts("-1");
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);bfs();}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！