迷宫问题

川长思鸟来 2022-08-05 04:28 189阅读 0赞

## 1102: 迷宫问题 ##

**时间限制: **1 Sec

**内存限制: **32 MB

**提交: **370

**解决: **130

[提交][Link 1] [状态][Link 2]

### 题目描述 ###

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

### 输入 ###

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

### 输出 ###

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

### 样例输入 ###

15 5S-\#\#\#-----\#\#---E\#------\#\#

### 样例输出 ###

### 提示 ###

### 来源 ###

[数据结构高分笔记][Link 3]

这一题是著名的bfs，跟dfs循环不一样，通过压进去和释放出去遍历到底！挺好！

#include<cstdio>
    #include<iostream>
    #include<queue>
    #include<string>
    #include<cstring>
    using namespace std;
    char map1[125][125];
    int vis[125][125];
    int to[4][2]={1,0,-1,0,0,1,0,-1};
    int n,m,sx,sy,ans;
    struct node
    {
        int x;
        int y;
        int step;
    };//定义一个结构体变量，里面有x,y,step
    int check(int x,int y)
    {
        if(x<0||x>=n||y<0||y>=m)
        {
            return 1;
        }
        if(vis[x][y]||map1[x][y]=='#')
        {
            return 1;
        }
        return 0;
    }//判断是否越界或者字符是否为'#'或者是否访问过！
    void bfs()
    {
        int i;
        queue<node>Q;
        node a,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();
            if(map1[a.x][a.y]=='E')
            {
                ans=a.step;
                return;
            }
            for(i=0;i<4;i++)
            {
                next=a;
                next.x+=to[i][0];
                next.y+=to[i][1];
                if(check(next.x,next.y))
                {
                    continue;
                }
                next.step=a.step+1;
                vis[next.x][next.y]=1;
                Q.push(next);
            }
        }
        ans=-1;
    }
    int main()
    {
        int times,i,j;
        cin>>times;
        while(times--)
        {
            scanf("%d%d",&n,&m);
            for(i=0;i<n;i++)
            {
                scanf("%s",map1[i]);
            }//先储存！
            for(i=0;i<n;i++)
            {
                for(j=0;j<m;j++)
                {
                    if(map1[i][j]=='S')
                    {
                        sx=i;
                        sy=j;
                    }
                }
            }//找'S'开始遍历！
            memset(vis,0,sizeof(vis));//清零
            bfs();
            cout<<ans<<endl;
        }
    }

[Link 1]: http://arena.acmclub.com/submitpage.php?id=1102
[Link 2]: http://arena.acmclub.com/problemstatus.php?id=1102
[Link 3]: http://arena.acmclub.com/problemset.php?search=%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E9%AB%98%E5%88%86%E7%AC%94%E8%AE%B0