牛客-走出迷宫

目录

牛客-走出迷宫

题目描述

输入描述:

输出描述:

输入

输出

解题思路：

---

牛客-走出迷宫

题目链接：牛客-走出迷宫

题目描述

小明现在在玩一个游戏，游戏来到了教学关卡，迷宫是一个N*M的矩阵。

小明的起点在地图中用“S”来表示，终点用“E”来表示，障碍物用“#”来表示，空地用“.”来表示。

障碍物不能通过。小明如果现在在点（x，y）处，那么下一步只能走到相邻的四个格子中的某一个：（x+1，y），（x-1，y），（x，y+1），（x，y-1）；

小明想要知道，现在他能否从起点走到终点。

输入描述:

本题包含多组数据。
每组数据先输入两个数字N,M
接下来N行，每行M个字符，表示地图的状态。
数据范围：
2<=N,M<=500
保证有一个起点S，同时保证有一个终点E.

输出描述:

每组数据输出一行，如果小明能够从起点走到终点，那么输出Yes，否则输出No

输入

3 3
S..
..E
...
3 3
S##
###
##E

输出

Yes
No

解题思路：

此题用DFS和BFS感觉都可以做，以下是BFS的解法，首先通过二维数组来储存迷宫地图，存好起点和终点的坐标位置，循环一个队列，将每个点上下左右去走，直到找到 或 队列走完，此时判断是否找到后输出，由于题目多组数据，所以外套一个循环，将输入的n m直接在while里面输入

#include
using namespace std;

#define ll long long
const ll maxn = 5e2 + 5;
int n, m;

int main()
{
    //多组数据，但是不能while(1)否则会报超时
    while(cin >> n >> m)
    {
        //用二维数组表示迷宫地图，1代表访问过与障碍物#，0代表可走位置
        int bk[maxn][maxn] = {0};
        //定义起点坐标，终点坐标，是否找到
        int x, y, x1, y1, flag = 0;
        //bfs队列
        queue> a;
        for(int i = 1; i <= n; i++)
        {
            char c;
            for(int j = 1; j <= m; j++)
            {
                cin >> c;
                //如果输入的字符是起点或者终点就记录此刻的下标记
                if(c == 'S')
                {
                    x = i;
                    y = j;
                }
                if(c == 'E')
                {
                    x1 = i;
                    y1 = j;
                }
                //如果是障碍物就赋值为1
                if(c == '#')bk[i][j] = 1;
                else bk[i][j] = 0;
            }
        }
        //预处理，将起点添加进队列
        a.push({x,y});
        bk[x][y] = 1;
        //一直遍历完整个迷宫
        while(a.size())
        {
            //取出队头下标
            int ux = a.front().first, uy = a.front().second;
            //取出后删除
            a.pop();
            //如果上下左右可行为止为终点，那么将flag标记为找到并终止循环（终点一定没障碍物）
            if(ux+1 == x1 && uy == y1 || ux-1 == x1 && uy == y1 || ux == x1 && uy+1 == y1 || ux == x1 && uy-1 == y1)
            {
                flag = 1;
                break;
            }
            //判断上下左右是否越界，并做复杂度优化（障碍物和访问过的点不添加）
            if(ux-1 != 0 && !bk[ux-1][uy])
            {
                a.push({ux-1,uy});
                bk[ux-1][y] = 1;
            }
            if(ux+1 != n+1 && !bk[ux+1][uy])
            {
                a.push({ux+1,uy});
                bk[ux+1][uy] = 1;
            }
            if(uy-1 != 0 && !bk[ux][uy-1])
            {
                a.push({ux,uy-1});
                bk[ux][uy-1] = 1;
            }
            if(uy+1 != m+1 && !bk[ux][uy+1])
            {
                a.push({ux,uy+1});
                bk[ux][uy+1] = 1;
            }
        }
        //判断flag输出
        if(flag)cout << "Yes" << endl;
        else cout << "No" << endl;
    }
    return 0;
}