解救小Q

题意：

小Q被邪恶的大魔王困在了迷宫里，love8909决定去解救她。迷宫里面有一些陷阱，一旦走到陷阱里，就会被困身亡:(，迷宫里还有一些古老的传送阵，一旦走到传送阵上，会强制被传送到传送阵的另一头。现在请你帮助love8909算一算，他至少需要走多少步才能解救到小Q？

思路：bfs

View Code

  1 #include <stdio.h>
  2 #include <string.h>
  3 struct node
  4 {
  5     int x1,y1,x2,y2;
  6 }belt[26];
  7 struct 
  8 {
  9     int x0,y0,count;
 10 }path[2500];
 11 int dis[4][2]={
 12     0,-1,1,0,0,1,-1,0
 13 };
 14 int cnt[26];
 15 bool vis[55][55];
 16 char map[55][55];
 17 int front;
 18 int finalx,finaly;
 19 int n,m;
 20 void bfs()
 21 {
 22     int rear=0,temp=0,mark=0;
 23     while(front<=rear&&!mark){
 24         while(front<=temp){
 25             if(path[front].x0==finalx&&path[front].y0==finaly){
 26                 printf("%d\n",path[front].count);
 27                 mark=1;
 28                 break;
 29             }
 30             for(int i=0;i<4;i++){
 31                 int nx=path[front].x0+dis[i][0];
 32                 int ny=path[front].y0+dis[i][1];
 33                 if(nx<0||nx>=m||ny<0||ny>=n||vis[ny][nx])
 34                 continue;
 35                 if(map[ny][nx]>='a'&&map[ny][nx]<='z'){
 36                     if(ny==belt[map[ny][nx]-'a'].y1&&nx==belt[map[ny][nx]-'a'].x1){
 37                         path[++rear].y0=belt[map[ny][nx]-'a'].y2;
 38                         path[rear].x0=belt[map[ny][nx]-'a'].x2;
 39                         path[rear].count=path[front].count+1;
 40                     }
 41                     else{
 42                         path[++rear].y0=belt[map[ny][nx]-'a'].y1;
 43                         path[rear].x0=belt[map[ny][nx]-'a'].x1;
 44                         path[rear].count=path[front].count+1;
 45                     }
 46                     vis[ny][nx]=true;
 47                     continue;
 48                 }
 49                 path[++rear].x0=nx;
 50                 path[rear].y0=ny;
 51                 path[rear].count=path[front].count+1;
 52                 vis[ny][nx]=true;
 53             }
 54             front++;
 55         }
 56         temp=rear;
 57     }
 58     if(!mark)
 59     printf("-1\n");
 60 }
 61 int main()
 62 {
 63     int t;
 64     scanf("%d",&t);
 65     while(t--){
 66         scanf("%d%d",&n,&m);
 67         getchar();
 68         memset(cnt,0,sizeof(cnt));
 69         memset(vis,false,sizeof(vis));
 70         front=-1;
 71         for(int i=0;i<n;i++){
 72             for(int j=0;j<m;j++){
 73                 scanf("%c",&map[i][j]);
 74                 if(map[i][j]>='a'&&map[i][j]<='z'){
 75                     if(cnt[map[i][j]-'a']==0){
 76                         cnt[map[i][j]-'a']++;
 77                         belt[map[i][j]-'a'].x1=j;
 78                         belt[map[i][j]-'a'].y1=i;
 79                     }
 80                     else{
 81                         belt[map[i][j]-'a'].x2=j;
 82                         belt[map[i][j]-'a'].y2=i;
 83                     }
 84                 }
 85                 else if(map[i][j]=='L'){
 86                     path[++front].x0=j;
 87                     path[front].y0=i;
 88                     path[front].count=0;
 89                     vis[i][j]=true;
 90                 }
 91                 else if(map[i][j]=='Q'){
 92                 finalx=j;
 93                 finaly=i;
 94                 }
 95                 else if(map[i][j]=='#')
 96                 vis[i][j]=true;
 97             }
 98             getchar();
 99         }
100         bfs();
101     }    
102 }