题目链接
/* 题意是是传统的迷宫加上一个条件，墙壁在k的整倍数时刻会消失，那么求到达出口的最短时间。 关键点在于某个点最多被走k次，标记vis[x][y][time%k]即可。 */ #include<queue> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=100+5; int vis[maxn][maxn][15]; int dir[4][2]={0,1,1,0,0,-1,-1,0}; char maze[maxn][maxn]; int sx,sy,ex,ey; int n,m,k; void init() { memset(vis,0,sizeof(vis)); } struct node { int x; int y; int time; }; int BFS() { node now; now.x=sx; now.y=sy; now.time=0; queue<node>que; que.push(now); while(!que.empty()) { now=que.front(); que.pop(); if(now.x==ex&&now.y==ey) return now.time; for(int i=0;i<4;i++) { int x=now.x+dir[i][0]; int y=now.y+dir[i][1]; int t=now.time+1; int mod=t%k; if(x>=1&&x<=n&&y>=1&&y<=m) { if(maze[x][y]!='#'&&vis[x][y][mod]==0) { vis[x][y][mod]=t; node next=(node){x,y,t}; que.push(next); } else if(maze[x][y]=='#'&&mod==0&&vis[x][y][mod]==0) { vis[x][y][mod]=t; node next=(node){x,y,t}; que.push(next); } } } } return -1; } int main () { int T;scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&k); init(); for(int i=1;i<=n;i++) { scanf("%s",maze[i]+1); for(int j=1;j<=m;j++) if(maze[i][j]=='Y') sx=i,sy=j; else if(maze[i][j]=='G') ex=i,ey=j; } int ans=BFS(); if(ans==-1) printf("Please give me another chance!\n"); else printf("%d\n",ans); } return 0; }