40分求助

Ssssshuai @ 2024-03-16 13:49:46

#include <iostream> 
#include <string>

using namespace std;

int n,m;
//迷宫 
char maze[110][110]; 
//标记
bool vis[110][110];
//移动操作
int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};

bool in(int x, int y)
{
    return 0<=x && x<n && 0<=y && y<m;
}

bool dfs(int x, int y)
{
    //结束条件 
    if (x==n && y==m)
    {
        return true;
    }

    //标记
    vis[x][y] = true;

    //移动
    for (int i=0; i<4; i++) 
    {
        int tx = x + dir[i][0];//当i等于0时，执行上移操作,
        int ty = y + dir[i][1];//接下来按逆时针移动

        //如果在范围内,并且不是墙壁，没有被标记过，就继续深度搜索 
        if (in(tx, ty) && maze[tx][ty] != '#' && !vis[tx][ty])
        {
            if (dfs(tx, ty))
            {
                return true;
            }
        } 
    }

    return false; 
}

int main()
{
    //输入迷宫地图
    cin >> n >> m;
    for (int i=1; i<=n; i++)    
    {
        for (int j=1; j<=m; j++)
        {
            cin >> maze[i][j];
        }
    }

    //DFS 
    if (dfs(1, 1))
    {
        cout << "Yes"; 
    }
    else 
    {
        cout << "No";
    }

    return 0;
}

by AKPC @ 2024-03-16 14:06:23

please bfs

by wjr_jok @ 2024-03-16 14:50:18

#include <iostream> 
#include <string>

using namespace std;

int n,m;
char maze[110][110]; 
bool vis[110][110];
int dir[4][2] = {{-1,0}, {0,-1}, {1,0}, {0,1}};

bool in(int x, int y)
{
    return 0<x && x<=n && 0<y && y<=m;
}

void dfs(int x, int y)
{
    if (x==n && y==m)
    {
        cout << "Yes"; 
        exit(0);
    }

    vis[x][y] = true;

    for (int i=0; i<4; i++) 
    {
        int tx = x + dir[i][0];
        int ty = y + dir[i][1];

        if (in(tx, ty) && maze[tx][ty] != '#' && !vis[tx][ty])
        {
            dfs(tx, ty);
        } 
    }
}

int main()
{
    cin >> n >> m;
    for (int i=1; i<=n; i++)    
    {
        for (int j=1; j<=m; j++)
        {
            cin >> maze[i][j];
        }
    }

    vis[1][1] = 1;

    dfs(1, 1);

    cout << "No";

    return 0;
}

1.在搜索时如果到达了目标点直接输出"Yes"并结束程序

2.修改一下你的in函数使得能递归到目标点

3.应先将起始点标记，否则会回头走

by wjr_jok @ 2024-03-16 14:50:41

@Ssssshuai

by qwe865 @ 2024-03-27 19:43:12

@wjr_jok 牛哔！