题目描述

小明置身于一个迷宫，请你帮小明找出从起点到终点的最短路程。
小明只能向上下左右四个方向移动。

输入

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：

‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过

输入数据保证有且仅有一个起点和终点。

输出

对于每组输入，输出从起点到终点的最短路程，如果不存在从起点到终点的路，则输出-1。

样例输入

1
5 5
S-###
-----
##---
E#---
---##

样例输出

9

代码

#include<stdio.h>
#include<string.h>
#include<queue>
using namespace std;
struct node{
    int x, y;
};
int step[110][110], n, m;
char a[110][110];
//BFS遍历 
void bfs(node h, node t)
{
    //记录当前坐标值 
	int tx, ty;
    //下一步可以向四个方向前进 
    int next[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
    node head, tail;
    queue<node> q;
    q.push(h);
    step[h.x][h.y] = 0;
    while(!q.empty()){
        head = q.front();
        q.pop();
        //分别尝试4个方向 
        for(int i = 0; i < 4; i++){
            tx = head.x + next[i][0];
            ty = head.y + next[i][1];
            //出边界，跳过 
            if(tx < 0 || ty < 0 || ty > m || tx > n)
                continue;
            if(step[tx][ty] == 0 && a[tx][ty] == '-' || a[tx][ty] == 'E'){
                tail.x = tx;
                tail.y = ty;
                q.push(tail);
                step[tx][ty] = step[head.x][head.y] + 1;
            }
            //到达终点 
            if(tx == t.x && ty == t.y)
                return;
        }
    }
}

int main()
{
    int T, i, j;
    node start, end;//分别记录起点和终点 
    scanf("%d", &T);
    while(T--){
    	//初始化步数 
        memset(step, 0, sizeof(step));
        scanf("%d%d", &n, &m);
        getchar();//吸收掉换行符 
        for(i = 0; i < n; i++){
            for(j = 0; j < m; j++){
                scanf("%c", &a[i][j]);
                if(a[i][j] == 'S'){
                    start.x = i;
                    start.y = j;  
                }
                else if(a[i][j] == 'E'){
                    end.x = i;
                    end.y = j;
                }
            }
            getchar();//吸收掉换行符 
        }
        bfs(start, end);
        printf("%d\n", step[end.x][end.y]);
    }
    return 0;
}