本文主要是介绍解救小Q(bfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
解救小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] != '#'){// upif(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] != '#') {//downif(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] != '#') {//leftif(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] != '#') {//rightif(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; }
这篇关于解救小Q(bfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
