1102:迷宫问题

题目描述

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

输入格式

输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘S’：起点
‘E’：终点
‘-’：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。

输出

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

样例输入

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

样例输出

9

#include<stdio.h>
#include<iostream>
#include<queue>
#define maxn 105
using namespace std;
    int t;
    int m,n;
    int sx,sy;//起点
    int ex,ey;//终点
    char map[maxn][maxn]; //存图
    int vis[maxn][maxn];//判断是否遍历过
    int dist[4][2]={{-1,0},{0,-1},{1,0},{0,1}};//四个方向
    int ans;
struct  node
{
    int x;
    int y;
    int step;
};
bool check(int x,int y)
{
    if(x>=0&&x<m&&y>=0&&y<n&&map[x][y]!='#'&&vis[x][y]==0)
        return true;
    return false;
}
void bfs()
{
    queue<node> q;
    node a;
    node next;
    a.x=sx;
    a.y=sy;
    a.step=0;
    vis[a.x][a.y]=1;
    q.push(a);       //始点入列
    while(!q.empty())//队列非空
    {
        a=q.front();//取首元素
        q.pop();<span style="font-family:'Lucida Console';">    //取出后删除首元素</span>
        for(int i=0;i<4;i++)//向四个方向遍历
    {
        next=a;
        next.x+=dist[i][0];
        next.y+=dist[i][1];
        next.step=a.step+1;
        if(next.x==ex&next.y==ey)<span style="font-family:'Lucida Console';">//判断是否是终点</span>
        {
            ans=next.step;
            return ;
        }
        if(check(next.x,next.y))//遍历标记，且入列
        {
            vis[next.x][next.y]=1;
            q.push(next);
        }

    }
    }
      ans=-1;//<span style="font-family:'Lucida Console';">死路</span>


}
int main()
{


    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&m,&n);
        for(int i=0;i<m;i++)

        {
            scanf("%s",&map[i]);
            for(int j=0;j<n;j++)
            {
                if(map[i][j]=='S')//得起点坐标
                {
                    sx=i;
                    sy=j;
                }
                 if(map[i][j]=='E')//得终点坐标
                 {
                     ex=i;
                     ey=j;
                 }
            }

        }
        bfs();
        printf("%d\n",ans);

    }
    return 0;

}