欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

K - 老鼠走迷宫

程序员文章站 2022-07-04 21:03:10
Description现在一只老鼠被困在了迷宫里!你需要判断老鼠能否走出迷宫。老鼠只能向上下左右四个方向移动。我们认为只要老鼠走到了迷宫的边界即算走出迷宫。Input第一行输入两个整数 nn, mm (1 \leqslant n, m \leqslant 100)(1⩽n,m⩽100) 表示迷宫地图的尺寸。接下来输入 nn 行,每行 mm 个字符,表示迷宫地图。其中 M 表示老鼠的位置,* 代表墙壁,. 代表空地。Output如果老鼠可以走出迷宫,则输出一行 Yes,否则输出一行 No。Sa...

Description

现在一只老鼠被困在了迷宫里!你需要判断老鼠能否走出迷宫。

老鼠只能向上下左右四个方向移动。我们认为只要老鼠走到了迷宫的边界即算走出迷宫。

Input

第一行输入两个整数 nn, mm (1 \leqslant n, m \leqslant 100)(1⩽n,m⩽100) 表示迷宫地图的尺寸。

接下来输入 nn 行,每行 mm 个字符,表示迷宫地图。其中 M 表示老鼠的位置,* 代表墙壁,. 代表空地。

Output

如果老鼠可以走出迷宫,则输出一行 Yes,否则输出一行 No。

Sample

Input

4 4
*.**
*..*
*.M*
****

Output
Yes

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

//上下左右
int X[] = {1,-1,0,0};
int Y[] = {0,0,-1,1};
bool vis[105][105];
char Map[105][105];
//是否成功的标志
bool flag;
int n,m;

void DFS(int x,int y)
{
    vis[x][y] = true;
    //到边界 = 找到出口
    if(x==0 || y==0 || x==n-1 || y==m-1)
    {
        flag = true;
        return ;
    }
    //上下左右
    for(int i=0;i<4;i++)
    {
        int dx = x+X[i];
        int dy = y+Y[i];
        if(Map[dx][dy] != '*' && !vis[dx][dy] && dx>=0 &&dx<n && dy>=0 && dy<m)
            DFS(dx,dy);
        //路通 && 没走过 && 没到边界
        //继续走
    }
}

int main()
{
    ios::sync_with_stdio(false);

    int x,y;
    flag = false;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        {
            cin>>Map[i][j];
            //记录老鼠的位置
            if(Map[i][j] == 'M')
            {
                x = i;
                y = j;
            }
        }
    DFS(x,y);
    if(flag)
        cout<<"Yes\n";
    else
        cout<<"No\n";
    return 0;
}

本文地址:https://blog.csdn.net/K_Programmer/article/details/110142436