FZU2285 迷宫问题 BFS求最短路-板子题

杨鹏伟

发布于 2020-09-11 00:06:29

5810

发布于 2020-09-11 00:06:29

文章被收录于专栏：ypwypw

Problem Description 洪尼玛今天准备去寻宝，在一个n*n （n行, n列）的迷宫中，存在着一个入口、一些墙壁以及一个宝藏。由于迷宫是四连通的，即在迷宫中的一个位置，只能走到与它直接相邻的其他四个位置（上、下、左、右）。现洪尼玛在迷宫的入口处，问他最少需要走几步才能拿到宝藏？若永远无法拿到宝藏，则输出-1。

Input 多组测试数据。

每组数据输入第一行为正整数n，表示迷宫大小。

接下来n行，每行包括n个字符，其中字符’.‘表示该位置为空地，字符’#'表示该位置为墙壁，字符’S’表示该位置为入口，字符’E’表示该位置为宝藏，输入数据中只有这四种字符，并且’S’和’E’仅出现一次。

Output 输出拿到宝藏最少需要走的步数，若永远无法拿到宝藏，则输出-1。

Sample Input

5 S.#… #.#.# #.#.# #…E #…

    #include<iostream>
    #include<queue>
    #include<cstring>
    #include<cstdio>
    using namespace std;
    
    const int MAX = 1000;
    char maza[MAX][MAX];//记录迷宫
    int step[MAX][MAX];//记录步数
    int sx,sy,ex,ey;//记录起点和终点
    
    struct Point
    {
        int x;
        int y;
    } point1,point2;//记录当前位置和下一位置
    
    int dir[4][2]= {{0,1},{0,-1},{-1,0},{1,0}};//上下左右四个方向
    
    queue<Point> Q;//队列
    
    int main()
    {
        int n,flag;
        while(cin>>n)
        {
            flag=0;
            while(!Q.empty())
                Q.pop();//清空队列
            memset(step,0,sizeof(step));//把记录步数的数组设为0
    
            for(int i=0;i<n;++i)
                scanf("%s",maza[i]);
    
            for(int i=0; i<n; ++i)
                for(int j=0; j<n; ++j)
                {
                    if(maza[i][j]=='S')
                        sx=i,sy=j;
                    if(maza[i][j]=='E')
                        ex=i,ey=j;//遍历图形找到起点和终点
                }
    
            step[sx][sy]=1;//设起点为1表示已经被访问过
            point1.x=sx;
            point1.y=sy;
            Q.push(point1);//把起点添加到队列
    
            while(!Q.empty())//当队列不为空时进行循环查找队列
            {
                point1=Q.front();//拿出队列首元素
                Q.pop();//拿出后移除首元素
                for(int i=0; i<4; ++i)
                {
                    point2.x=point1.x+dir[i][0];
                    point2.y=point1.y+dir[i][1];
                    if( point2.x >= 0 && point2.y >= 0 && point2.x < n && point2.y < n && !step[point2.x][point2.y] && maza[point2.x][point2.y] != '#' )
                    {
                        //如果下一个节点不出边界，没被访问过且不是墙，则步数+1
                        step[point2.x][point2.y]=step[point1.x][point1.y]+1;
                        Q.push(point2);
                    }
                }
                if(step[ex][ey]!=0)
                {//找到出口
                    flag=1;
                    break;
                }
            }
            if(flag)
                cout<<step[ex][ey]-1<<endl;//因为起点为1，故需减去1则为步数
            else
                cout<<-1<<endl;
        }
        return 0;
    }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-02-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

input