hdu2574
1857 ワード
bfsこの問題は止められないように要求されているようです~~
visは3次元で考えればわかる
visは3次元で考えればわかる
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
char map[105][105];
int xx[4]={0,1,0,-1};
int yy[4]={1,0,-1,0};
int vis[105][105][12];
int r,c,k;
struct node
{
int x,y,d;
node(int x1,int y1,int d1)
{
x=x1;
y=y1;
d=d1;
}
};
int bfs(int x,int y)
{
vis[x][y][0]=1;
queue<node> q;
q.push(node(x,y,0));
while(!q.empty())
{
node t=q.front();
q.pop();
x=t.x;
y=t.y;
int time=t.d;
if(map[x][y]=='G')
return t.d;
int i;
for(i=0;i<4;i++)
{
int tx=x+xx[i];
int ty=y+yy[i];
if(tx<0||tx>=r||ty<0||ty>=c)
continue;
if(vis[tx][ty][(time+1)%k])
continue;
vis[tx][ty][(time+1)%k]=1;
if(map[tx][ty]=='#')
{
if((time+1)%k==0)
q.push(node(tx,ty,time+1));
}
else
q.push(node(tx,ty,time+1));
}
}
return -1;
}
int main()
{
int t;
scanf("%d",&t);
int cas=0;
for(cas=0;cas<t;cas++)
{
scanf("%d%d%d",&r,&c,&k);
int i,j;
int sx,sy;
memset(vis,0,sizeof(vis));
for(i=0;i<r;i++)
{
scanf("%s",map[i]);
for(j=0;j<c;j++)
if(map[i][j]=='Y')
sx=i,sy=j;
}
int temp=bfs(sx,sy);
if(temp==-1)
printf("Please give me another chance!
");
else
printf("%d
",temp);
}
return 0;
}