学步园

广搜，，

hash[x][y][step%k]记录x,y位置step%k这种情况走过没有

#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
char map[110][110];
int n,m,k,hash[110][110][11];
int sx,sy,ex,ey;
int dir[4][2]={0,1,1,0,0,-1,-1,0};
struct op
{
	int x,y,step;
}cur,next;
int judge(int x,int y)
{
	if(x>=0&&x<n&&y>=0&&y<m)
		return 1;
	return 0;
}
int bfs()
{
	int i,j,x,y,step;
	queue<op>Q;
	cur.step=0;
	cur.x=sx;
	cur.y=sy;
	Q.push(cur);
	while(!Q.empty())
	{
		cur=Q.front();
		Q.pop();
		if(cur.x==ex&&cur.y==ey)
			return cur.step;
		for(i=0;i<4;i++)
		{
			x=cur.x+dir[i][0];
			y=cur.y+dir[i][1];
			step=cur.step+1;
			if(judge(x,y)&&hash[x][y][step%k]==0)
			{
				next.x=x;
				next.y=y;
				next.step=step;
				if((map[next.x][next.y]=='#'&&next.step%k==0)||map[x][y]=='.'||map[x][y]=='G'||map[x][y]=='Y')
					Q.push(next);
				hash[x][y][next.step%k]=1;
			}
			
		}
	}
	return -1;
}
int main()
{
	int i,j,t;
	scanf("%d",&t);
	while(t--)
	{
		memset(hash,0,sizeof(hash));
		scanf("%d%d%d",&n,&m,&k);
		for(i=0;i<n;i++)
			scanf("%s",map[i]);
		for(i=0;i<n;i++)
			for(j=0;j<m;j++)
			{
				if(map[i][j]=='Y')
				{
					sx=i;
					sy=j;
				}
				if(map[i][j]=='G')
				{
					ex=i;
					ey=j;
				}
			}
			j=bfs();
			if(j==-1)puts("Please give me another chance!");
			else printf("%d\n",j);
	}
	return 0;
}