题目描述

Simple最近刷题（打游戏）刷多了，一觉醒来发现自己到了一个迷宫里，怎么也出不去了。这时传来了一句话，告诉Simple必须按顺序收集完所有的宝石，才能出迷宫。所谓的顺序，就是按照每块宝石上英文字母的顺序。迷宫里面还有一些传送门，可以传送到任意一个另外的传送门的位置。（你走到一个不是空地上的地方的时候，就一定会触发相应事件，不可拒绝，从一个传送门传送到另一个传送门不用再次传送）。每走一步花费一个单位时间，传送门到另外一个传送门不需要时间。Simple初始就在字母为A的宝石的位置上（开局一宝石，其他全靠找）。

当Simple收集完所有宝石的时候就被传送出迷宫。

Simple还要赶回去刷题（打游戏），你们能告诉他最少需要多长时间才能回去吗？如果不可能出去就输出Impossible。 输入

多组实例，每组输入一个n，表示迷宫的大小为n*n (n <= 10) 下面n行每行n个字符 ‘.’表示空地， ‘#’表示墙，不可以通过 ‘$’表示一个传送门 大写字母表示宝石

输出

每个实例输出一个数字，表示最少需要的时间，如果不能逃出迷宫，就输出Impossible。 样例输入

5 A….

.

..B.. .#### C.DE.

2 AC .B

2 A#

B

3 A .…. B 样例输出

15 3 Impossible 2

zz 了，这种题就是烦人，让你知道大致思路，然后我一直wa。

标程思路 还是很清晰的。自己写的时候总是zz【学习一波bfs的标准操作】

代码

#include<bits/stdc++.h> #define LL long long using namespace std; const int MAXN = 1e2; const int MAXM = 1e5; struct Door{ int x,y; }d[MAXN]; struct Node{ int x,y,step,cnt; }; int dcnt,nsize; int n,m; char mp[MAXN][MAXN]; Node S; void getmap(){ getchar(); dcnt=0;nsize=0; for(int i=0;i<n;i++){ scanf("%s",mp[i]); for(int j=0;j<n;j++){ if(mp[i][j]=='$') d[dcnt++]={i,j}; if(mp[i][j]=='A') S={i,j,0,1}; if(mp[i][j]>='A'&&mp[i][j]<='Z') nsize++; } getchar(); } } int vis[MAXN][MAXN]; int to[][2]={1,0,-1,0,0,1,0,-1}; void bfs(){ queue<Node >Q; memset(vis,0,sizeof(vis)); vis[S.x][S.y]=1;Q.push(S); Node now,nexts; while(!Q.empty()){ now=Q.front();Q.pop(); if(now.cnt==nsize) { printf("%d\n",now.step); return ;} for(int i=0;i<4;i++){ int nx=now.x+to[i][0]; int ny=now.y+to[i][1]; if(nx<0||ny<0||nx>=n||ny>=n) continue; if(vis[nx][ny]||mp[nx][ny]=='#') continue; if(mp[nx][ny]=='$') { for(int j=0;j<dcnt;j++){ if(vis[d[j].x][d[j].y]) continue; if(nx==d[j].x&&ny==d[j].y) continue; nexts={d[j].x,d[j].y,now.step+1,now.cnt}; vis[d[j].x][d[j].y]=1; Q.push(nexts); } continue; } if(mp[nx][ny]>='A'&&mp[nx][ny]<='Z'&&mp[nx][ny]>'A'+now.cnt) continue;//没有走过的宝石不能够走 if(mp[nx][ny]>='A'&&mp[nx][ny]<='Z'&&mp[nx][ny]=='A'+now.cnt) { nexts={nx,ny,now.step+1,now.cnt+1}; while(!Q.empty()) Q.pop(); memset(vis,0,sizeof(vis)); vis[nx][ny]=1; Q.push(nexts); break; } nexts={nx,ny,now.step+1,now.cnt}; vis[nx][ny]=1; Q.push(nexts); } } puts("Impossible"); } int main(){ while(scanf("%d",&n)!=EOF){ getmap(); bfs(); } return 0; }