题目链接

题目描述

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

我是用多次的bfs过得，就是先找到B这个宝石，在从B的位置开始bfs，再找下一个宝石，直到找到最后一个宝石，注意已经找到宝石的位置要变为空地(因为这里错了好几次),遇到不是当前要找的宝石要当做墙来处理

完整代码如下：

#include<cstdio> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<algorithm> #include<queue> using namespace std; const int MAX_N = 15; char Map[MAX_N][MAX_N]; bool used[MAX_N][MAX_N]; const int xx[] = {0,1,0,-1}; const int yy[] = {-1,0,1,0}; int n; struct node{ int x,y; int f; }es,be,fi[110]; int top_fi; char max_ch; node bfs(node s,char ch){ //目标宝石为ch+1 queue<node> q; memset(used,false,sizeof(used)); q.push(s); Map[s.x][s.y] = '.';//已经找到宝石的地方更新为空地 used[s.x][s.y] = true; while(!q.empty()){ es = q.front();q.pop(); if(Map[es.x][es.y] == ch+1){ return es; } node nx; for(int i=0;i<4;i++){ nx.x = es.x + xx[i]; nx.y = es.y + yy[i]; nx.f = es.f + 1; if(nx.x < 0 || nx.x >= n || nx.y < 0 || nx.y >= n) continue; if(Map[nx.x][nx.y] == '#' || used[nx.x][nx.y]) continue; if(Map[nx.x][nx.y] == '$'){ used[nx.x][nx.y] = true; for(int i=1;i<=top_fi;i++){ if(used[fi[i].x][fi[i].y] == false){ es = fi[i]; es.f = nx.f; q.push(es); used[fi[i].x][fi[i].y] = true; } } } if(Map[nx.x][nx.y] == '.' || Map[nx.x][nx.y] == (ch + 1)){ used[nx.x][nx.y] = true; q.push(nx); } } } return node{0,0,-1}; } int main(void){ while(scanf("%d",&n) != EOF){ for(int i=0;i<n;i++) scanf("%s",Map[i]); max_ch = 0;top_fi = 0; for(int i=0;i<n;i++) for(int j=0;j<n;j++){ if(Map[i][j] <='Z' && Map[i][j] >='A' && Map[i][j] > max_ch) max_ch = Map[i][j]; if(Map[i][j] == '$'){ es.x = i;es.y = j; es.f = 0; fi[++top_fi] = es; } if(Map[i][j] == 'A'){ be.x = i;//记录第一个宝石，即开始的位置。 be.y = j; be.f = 0; } } char ch = 'A'; int res = 0; node ti = be; while(ch != max_ch){ ti = bfs(ti,ch); if(ti.f == -1){//表示未找到目标宝石 break; } else{ res += ti.f;//加上找到目标宝石的最小步数 ch += 1; ti.f = 0; } } if(ch == max_ch) printf("%d\n",res); else printf("Impossible\n"); } return 0; }