描述
小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了。
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <queue>
#define MAXN 55
using 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
",ans);
}
return 0;
}