uestc oj 1002 解救小Q

解救小Q

Description

小Q被邪恶的大魔王困在了迷宫里，love8909决定去解救她。
迷宫里面有一些陷阱，一旦走到陷阱里，就会被困身亡:(，迷宫
里还有一些古老的传送阵，一旦走到传送阵上，会强制被传送到
传送阵的另一头。

现在请你帮助love8909算一算，他至少需要走多少步才能解
救到小Q？

Input

第一行为一个整数T，表示测试数据组数。

每组测试数据第一行为两个整数N，M，(N, M)表示
迷宫的长和宽。

接下来有N行，每行M个字符，是迷宫的具体描述。

.表示安全的位置
#表示陷阱，
Q表示小Q的位置
L表示love8909所在位置，
数据保证love8909只有一个，数据也保证小Q只有一个。

小写字母a-z表示分别表示不同的传送阵，数据保证传送阵
两两配对。

Output

每组数据输出一行，解救小Q所需的最少步数，如果无论如何都
无法救小Q，输出-1。

Sample Input

2

5 5
....L
.###.
b#b#a
##.##
...Qa

5 5
....L
.###.
.#.#.
##.##
...Q.
Sample Output

3
-1

 

  这一题就是普通的广度优先搜索求取最短路的题目。
  不过这个题目添加了传动带和陷阱的这两个障碍。
  这一题也是有读入回车的getchar处理因为读入的都是字符的。
  单独开一个数组【26】【2】的存放传送带 用结构体来表示 有表示是第一个节点还是第二个节点的
 flag 还有坐标row col还有 值s
  在广搜的时候遇到传送带就传送过去。
  在传送带的处理上有两个问题是要注意的，一是在初始化的时候判断好那个已经初始化还有那个没有初始化，
  在传动的时候要注意是从哪一个传动到另一个。
  注意在搜索的时候边界条件的判断。不能出界的。
 

#include<cstdio> #include<cstring>char map[55][55]; int vis[55][55]; struct node {int step;int row;int col; }que[55*55]; struct gate {char s;int row;int col;int flag; }gate[26][2]; int dir[4][2]={0,1,0,-1,-1,0,1,0}; int T,N,M;int main() {//freopen("1.txt","r",stdin);scanf("%d",&T);getchar();while(T--){scanf("%d%d",&N,&M);getchar();memset(vis,0,sizeof(vis));for(int i=0;i<26;i++){gate[i][0].flag =0;gate[i][0].flag =0; }int head = 0;int tail = 0;int mark =0;for(int i=0;i<N;i++){for(int j=0;j<M;j++){scanf("%c",&map[i][j]);que[tail].step =0; if(map[i][j]=='L'){map[i][j] = '#', que[tail].row =i;que[tail].col =j;que[tail].step =0;vis[i][j]=1;tail++; }if(map[i][j]>='a'&&map[i][j]<='z') {int a = (int)map[i][j]-'a'; if(gate[a][0].flag==0){gate[a][0].row = i;gate[a][0].col = j;gate[a][0].flag = 1;}else{gate[a][1].row = i; gate[a][1].col = j;gate[a][1].flag = 1; }}}getchar();}while(head<tail) {int nx = que[head].row; int ny = que[head].col;int temp = head;for(int i =0;i<4;i++){int nx2 = nx + dir[i][0];int ny2 = ny + dir[i][1]; if(nx2>=N||nx2<0||ny2>=M||ny2<0||vis[nx2][ny2]||map[nx2][ny2]=='#')continue;if(map[nx2][ny2]=='Q') {mark =1;printf("%d\n",que[temp].step+1);}if(map[nx2][ny2]=='.'){que[tail].row = nx2 ;que[tail].col = ny2 ;que[tail].step = que[temp].step+1;tail++;}else{int j = (int)map[nx2][ny2]-'a';if(nx2==gate[j][0].row&&ny2==gate[j][0].col){que[tail].row = gate[j][1].row;que[tail].col = gate[j][1].col;que[tail].step = que[temp].step+1;gate[j][1].flag =0; tail++;}else{que[tail].row = gate[j][0].row;//printf("%d",gate[j][0].row);que[tail].col = gate[j][0].col;que[tail].step = que[temp].step+1; gate[j][0].flag =0;tail++;}}vis[nx2][ny2]=1; }head++;}if(mark==0)printf("-1\n");}}

 

 

 

总结

以上是生活随笔为你收集整理的uestc oj 1002 解救小Q的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。