3344 迷宫
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold
题目描述 Description
小刚在迷宫内，他需要从A点出发，按顺序经过B,C,D……，到达最后一个点，再回到A点。迷宫内有些障碍，问至少走几步。
输入描述 Input Description
第一行有三个数n，m表示迷宫有n行，m列。
第2行到第n+1行，每行m个字符，可能是’A’..’Z’,’2’,’0’ 其中，2表示障碍，0表示可以走。’A’..’Z’也可以走。
输出描述 Output Description
至少走几步可以按规定走完，如果不行，输出“Impossible”
样例输入 Sample Input
5 5
A002B
022C0
000D0
00222
0000E
样例输出 Sample Output
26
数据范围及提示 Data Size & Hint
0%的数据满足：1<=n<=10 1<=m<=10 字母为“A”..“B”。
30%的数据满足：1<=n<=10 1<=m<=10 字母为“A”..“G”。
50%的数据满足：1<=n<=10 1<=m<=10 字母为“A”..“Z”。
10%的数据满足：1<=n<=100 1<=m<=100 字母为“A”..“B”。
30%的数据满足：1<=n<=100 1<=m<=100 字母为“A”..“G”。
100%的数据满足：1<=n<=100 1<=m<=100 字母为“A”..“Z”。
bfs
以A为起点以B为终点，以B为起点以C为终点、、、以此类推，跑sum遍bfs找出每一个点到它下一个点的最小值，然后累加就可以了。
不要忘了判断没有路的情况
#include#include #include #include #include #include #define N 210using namespace std;char ch;bool flag;int dis[N][N],map[N][N];int n,m,sx,sy,ex,ey,sum,ans;int xx[4]={ 0,0,1,-1},yy[4]={ 1,-1,0,0};int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();} return x*f;}struct Node{ int x,y;}node[50],que;queue q;void bfs(int sx,int sy){ while(!q.empty()) q.pop(); memset(dis,0x3f3f3f3f,sizeof(dis)); dis[sx][sy]=0; que.x=sx,que.y=sy,q.push(que); while(!q.empty()) { Node p=q.front();q.pop(); if(p.x==ex&&p.y==ey) {ans+=dis[ex][ey]; return ;} for(int i=0;i<4;i++) { int fx=p.x+xx[i],fy=p.y+yy[i]; if(fx<0||fy<0||fx>n||fy>m||!map[fx][fy]) continue; if(dis[fx][fy]<=dis[p.x][p.y]+1) continue; dis[fx][fy]=dis[p.x][p.y]+1; que.x=fx,que.y=fy; q.push(que); } } flag=true;}int main(){ n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>ch; if(ch=='2') map[i][j]=0; else map[i][j]=1; if(ch>='A'&&ch<='Z') { sx=ch-'A'+2; sum=max(sx,sum); node[sx].x=i; node[sx].y=j; } } for(int i=2;i<=sum;i++) { sx=node[i].x,sy=node[i].y; if(i==sum) ex=node[2].x,ey=node[2].y; else ex=node[i+1].x,ey=node[i+1].y; bfs(sx,sy); } if(flag) printf("Impossible"); else printf("%d",ans); return 0;}