本文主要是介绍hdu(2102) A计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
/*题意很容易理解；
值得注意的是：把那些不能走的转化为墙；
一；如果#的对面是“*”，则将#变为’*‘；
二；两层对应的都是’#‘则把他们都转化为’*‘；
错几次的原因；
一；bfs中不满足是输出负一，不能是零，找了好久才找到这个错误；
二；用了三维坐标，不好控制；
三；上面的转化没转化完；
四，visit放在外边超时了；*/
#include"stdio.h"
#include"string.h"
#include"queue"
char map[2][100][100];
int visit[2][100][100];
int dir[4][2]={-1,0, 0,1, 1,0, 0,-1};
int n,m,sx,sy,ss;
using namespace std;
struct point
{
int x,y;
int k,step;
};
int judge(int k,int x,int y)
{
if(x>=0&&x<n&&y>=0&&y<m&&map[k][x][y]!='*'&&visit[k][x][y]==0)
return 1;
return 0;
}
int bfs(int k,int x,int y)
{
int i;
queue<point>q;
memset(visit,0,sizeof(visit));
point cur,next;
cur.k=k;cur.x=x;
cur.y=y;cur.step=0;
q.push(cur);
visit[k][x][y]=1;
while(!q.empty())
{
next=q.front();
q.pop();
if(next.k==ss&&next.x==sx&&next.y==sy)
return next.step;
for(i=0;i<4;i++)
{
x=next.x+dir[i][0];
y=next.y+dir[i][1];
k=next.k;
if(judge(k,x,y))
{
if(map[k][x][y]=='#')
{
visit[k][x][y]=1;//这个不能省略，虽然外面也有,但已经不是同一层了，是对面的一层，所以这个必须要；
if(k==0)
k=1;
else
k=0;
}
visit[k][x][y]=1;
cur.x=x,cur.y=y,cur.k=k;
cur.step=next.step+1;
q.push(cur);
}
}
}
return -1;
}
int main()
{
int i,j,k,tt,w;
scanf("%d",&w);
while(w--)
{
scanf("%d%d%d",&n,&m,&tt);
for(i=0;i<2;i++)
for(j=0;j<n;j++)
{
scanf("%s",map[i][j]);
for(k=0;k<m;k++)
{
if(map[i][j][k]=='P')
{
ss=i;sx=j;sy=k;
}
}
}
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
if(map[0][i][j]=='#'&&map[1][i][j]=='*')
map[0][i][j]='*';
else if(map[1][i][j]=='#'&&map[0][i][j]=='*')
map[1][i][j]='*';
else if(map[0][i][j]=='#'&&map[1][i][j]=='#')
map[0][i][j]=map[1][i][j]='*';
}
if(bfs(0,0,0)==-1)
printf("NO\n");
else if(bfs(0,0,0)<=tt)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
这篇关于hdu(2102) A计划的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
