解救小Q 
Time Limit(Common/Java):1000MS/3000MS Memory Limit:65536KByte
Total Submit: 16 Accepted: 3
Total Submit: 16 Accepted: 3
Description
小Q被邪恶的大魔王困在了迷宫里，love8909决定去解救她。迷宫里面有一些陷阱，一旦走到陷阱里，就会被困身亡:(，迷宫里还有一些古老的传送阵，一旦走到传送阵上，会强制被传送到传送阵的另一头。
现在请你帮助love8909算一算，他至少需要走多少步才能解救到小Q？ (上下左右四个方向走，传送门可以多次使用)
Input
第一行为一个整数T，表示测试数据组数。每组测试数据第一行为两个整数N，M，(1 <= N, M <= 50)表示迷宫的长和宽。接下来有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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
const int INF = 0x7fffffff;
using namespace std;
const int maxn = 110;
char g[maxn][maxn];
int n, m;
int used[maxn][maxn];//保存从s到这点最小步数
string trace[maxn][maxn];//记录路径.
struct info {
int x;
int y;
int time;
};
info start, endx;
queue<info> Q;
void init() {
while(!Q.empty()) Q.pop();
memset(g, '\0', sizeof(g));
}
void bfs() {
Q.push(start);
info tmp, in;
while(!Q.empty()) {
tmp = Q.front();
Q.pop();
if(tmp.x - 1 >= 1 && g[tmp.x-1][tmp.y] != '#'){// up
if(tmp.time + 1 < used[tmp.x-1][tmp.y]) {
used[tmp.x-1][tmp.y] = tmp.time + 1;
trace[tmp.x-1][tmp.y] = trace[tmp.x][tmp.y] + 'N';
in.x = tmp.x - 1;
in.y = tmp.y;
in.time = used[tmp.x-1][tmp.y];
Q.push(in);
}
}
if(tmp.x + 1 <= n && g[tmp.x+1][tmp.y] != '#') {//down
if(tmp.time + 1 < used[tmp.x+1][tmp.y]) {
used[tmp.x+1][tmp.y] = tmp.time + 1;
trace[tmp.x+1][tmp.y] = trace[tmp.x][tmp.y] + 'S';
in.x = tmp.x + 1;
in.y = tmp.y;
in.time = used[tmp.x+1][tmp.y];
Q.push(in);
}
}
if(tmp.y - 1 >= 1 && g[tmp.x][tmp.y-1] != '#') {//left
if(tmp.time + 1 < used[tmp.x][tmp.y-1]) {
used[tmp.x][tmp.y-1] = tmp.time + 1;
trace[tmp.x][tmp.y-1] = trace[tmp.x][tmp.y] + 'W';
in.x = tmp.x;
in.y = tmp.y - 1;
in.time = used[tmp.x][tmp.y-1];
Q.push(in);
}
}
if(tmp.y + 1 <= m && g[tmp.x][tmp.y+1] != '#') {//right
if(tmp.time + 1 < used[tmp.x][tmp.y+1] ) {
used[tmp.x][tmp.y+1] = tmp.time + 1;
trace[tmp.x][tmp.y+1] = trace[tmp.x][tmp.y] + 'E';
in.x = tmp.x;
in.y = tmp.y + 1;
in.time = used[tmp.x][tmp.y+1];
Q.push(in);
}
}
}
if(used[endx.x][endx.y] == INF) {
printf("Can't eat it!\n");
} else {
cout << trace[endx.x][endx.y] << endl;
}
}
int main()
{
int i, j;
while(scanf("%d%d", &n, &m) != EOF) {
init();
for(i = 1; i <= n; i++) {
scanf("%s", g[i]+1);
}
for(i = 1; i <= n; i++) {
for(j = 1; j <= m; j++) {
if(g[i][j] == 'S') {
start.x = i;
start.y = j;
start.time = 0;
used[i][j] = 0;//开始步数.
}
if(g[i][j]=='E') {
endx.x = i;
endx.y = j;
}
if(g[i][j] != 'S')
used[i][j] = INF;//初始化每个值.
trace[i][j].clear();
}
}
bfs();
}
return 0;
}