涪陵网站建设 优帮云,以什么主题做网站好,一二年级的科技小制作,在线网页代理极光http://acm.hdu.edu.cn/showproblem.php?pid2579 题目大意#xff1a;给定 r * c 的迷宫#xff0c;还有一个整数 k 。迷宫中“.”表示可以走#xff0c;“#”表示墙#xff0c;当时间为k的倍数时#xff0c;这些墙会消失。求从起点“Y”到终点“G”的最短时间。#xf…http://acm.hdu.edu.cn/showproblem.php?pid2579 题目大意给定 r * c 的迷宫还有一个整数 k 。迷宫中“.”表示可以走“#”表示墙当时间为k的倍数时这些墙会消失。求从起点“Y”到终点“G”的最短时间。人不能呆在一点不动。 #includeiostream
#includestdio.h
#includestring.h
#includestdlib.h
#includemath.h
#includequeue
#includealgorithm
#define N 105
using namespace std;
char map[N][N];
int step[N][N][10];//多加一维记录(time%k)
int r,c,k,x_s,y_s,x_e,y_e;
int dir[4][2]{0,1,0,-1,1,0,-1,0};
struct node
{int x,y,mod;
};
int BFS()
{int i;queuenodeq;node now,next;now.xx_s;now.yy_s;now.mod0;memset(step,-1,sizeof(step));step[now.x][now.y][now.mod]0;q.push(now);while(!q.empty()){nowq.front();q.pop();if(now.xx_e now.yy_e) return step[now.x][now.y][now.mod];for(i0;i4;i){next.xnow.xdir[i][0];next.ynow.ydir[i][1];next.mod(now.mod1)%k;if(next.x0 || next.xr || next.y0 ||next.yc) continue;if(step[next.x][next.y][next.mod]!-1) continue;if(map[next.x][next.y]# next.mod!0) continue;step[next.x][next.y][next.mod]step[now.x][now.y][now.mod]1;q.push(next);}}return -1;
}
int main()
{int T,i,j,ans;scanf(%d,T);while(T--){scanf(%d%d%d,r,c,k);for(i0;ir;i){scanf(%s,map[i]);for(j0;map[i][j];j){if(map[i][j]Y){x_si;y_sj;map[i][j].;}if(map[i][j]G){x_ei;y_ej;map[i][j].;}}}ansBFS();if(ans-1) printf(Please give me another chance!\n);else printf(%d\n,ans);}return 0;
}
