描述
小Q被邪恶的大魔王困在了迷宫里，love8909决定去解救她。迷宫里面有一些陷阱，一旦走到陷阱里，就会被困身亡:(，迷宫里还有一些古老的传送阵，一旦走到传送阵上，会强制被传送到传送阵的另一头。
现在请你帮助love8909算一算，他至少需要走多少步才能解救到小Q？ (上下左右四个方向走，传送门可以多次使用)
输入
第一行为一个整数T，表示测试数据组数。每组测试数据第一行为两个整数N，M，(1
<= N, M <=
50)表示迷宫的长和宽。接下来有N行，每行M个字符，是迷宫的具体描述。
‘.‘表示安全的位置，‘#‘表示陷阱，
‘Q‘表示小Q的位置，‘L‘表示love8909所在位置，
数据保证love8909只有一个，数据也保证小Q只有一个。小写字母‘a‘-‘z‘表示分别表示不同的传送阵，数据保证传送阵两两配对。
输出
每组数据输出一行，解救小Q所需的最少步数，如果无论如何都无法救小Q，输出-1。
样例输入
2
5 5
....L
.###.
b#b#a
##.##
...Qa
5 5
....L
.###.
.#.#.
##.##
...Q.
样例输出
3
-1
题目来源
cjx在做这题的时候真心难受(╯﹏╰），超时！后来发现每次标记后的点并不完全是经过的点，而是传送时候的点。泪奔！
修改后出现了WA，cjx有种苦尽甘来的感觉。事实是这样，很快就想到有一种特殊的情况没有考虑到。此案例通过后终于AC了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106 |
#include <stdio.h>#include <string.h>#include <iostream>#include <queue>#define MAXN 55using
namespace std;int T,M,N;int csMap[27][5];char
m[MAXN][MAXN];int
flag[MAXN][MAXN];int
ans,bx,by,ex,ey;int
dir[4][2]={ {0,1},{0,-1},{1,0},{-1,0} };struct
Node{ int
x; int
y; int
step; friend
bool operator <(Node a, Node b){ return
a.step>b.step; }};//存储传送点 void
save(char
a, int
x, int
y){ int
pos=a-‘a‘; if(csMap[pos][0]==0){ csMap[pos][1]=x; csMap[pos][2]=y; csMap[pos][0]=1; }else
if(csMap[pos][0]==1){ csMap[pos][3]=x; csMap[pos][4]=y; }}int
bfs(){ priority_queue<Node> Q; Node n1; n1.x=bx; n1.y=by; n1.step=0; flag[bx][by]=1; Q.push(n1); while(!Q.empty()){ Node now=Q.top(); Q.pop(); if( now.x==ex && now.y == ey )return
now.step; for(int
i=0; i<4; i++){ Node t; t.x=now.x+dir[i][0]; t.y=now.y+dir[i][1]; t.step=now.step+1; if( 1<=t.x&&t.x<=N && 1<=t.y&&t.y<=M &&!flag[t.x][t.y] && m[t.x][t.y]!=‘#‘){ flag[t.x][t.y]=1; if(‘a‘<=m[t.x][t.y] && m[t.x][t.y]<=‘z‘){ int
pos=m[t.x][t.y]-‘a‘; if(csMap[pos][1]==t.x && csMap[pos][2]==t.y){ t.x=csMap[pos][3]; t.y=csMap[pos][4]; }else{ t.x=csMap[pos][1]; t.y=csMap[pos][2]; } } Q.push(t); } } } return
-1;}int
main(){ scanf("%d",&T); while(T--){ scanf("%d %d",&N,&M); for(int
i=0; i<27; i++){ //0表示没有放任何的传送点 csMap[i][0]=0; } for(int
i=1; i<=N; i++){ getchar(); for(int
j=1; j<=M; j++){ scanf("%c",&m[i][j]); if( ‘a‘<=m[i][j] && m[i][j]<=‘z‘
){ save(m[i][j],i,j); } if( m[i][j]==‘L‘){ bx=i; by=j; } if( m[i][j]==‘Q‘){ ex=i; ey=j; } flag[i][j]=0; } } ans=bfs(); printf("%d\n",ans); } return
0;} |
原文：http://www.cnblogs.com/chenjianxiang/p/3544331.html