悬关！感觉逻辑对的，但是样例过不了！不知道为什么debug发现走不到最后一个点

coool @ 2023-08-30 12:13:56

#include <bits/stdc++.h>
using namespace std;

int n, m;
char c[105][105];
int vis[105][105];
int direc[4][2] = {{0, -1},{-1, 0}, {0,1}, {1, 0}};

bool check(int x, int y)
{
    if (x < 1 || y < 1 || x > n || y > m || vis[x][y] || c[x][y] == '#')
        return false;
    return true;
}

bool dfs(int x, int y)
{
    if (x == n && y == m)
        return true;
    if (c[n][m] == '#')
        return false;

    for (int i = 0; i < 4; i++)
    {
        int xx = x + direc[i][0];
        int yy = y + direc[i][1];

        if (check(xx, yy))
        {
            cout << x << " " << y << endl;
            vis[xx][yy] = 1;
            dfs(xx, yy);
            vis[xx][yy] = 0;

        }
    }

    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> c[i][j];
        }
    }
    vis[1][1] = 1;
    if (dfs(1, 1))
    {
        cout << "Yes" << endl;
    }
    else
        cout << "No" << endl;
    return 0;
}

by lujunxuan123 @ 2023-08-30 12:20:28

@coool 为啥要吧dfs写成bool

by ryf_loser @ 2023-08-30 12:21:24

@coool 你的返回只是返回到上一层，而不是直接返回到主函数。

by lujunxuan123 @ 2023-08-30 12:21:25

是没学过搜索吗

by ryf_loser @ 2023-08-30 12:23:20

@coool

#include <bits/stdc++.h>
using namespace std;

int n, m;
char c[105][105];
int vis[105][105];
int direc[4][2] = {{0, -1},{-1, 0}, {0,1}, {1, 0}};
bool flag=0;

bool check(int x, int y)
{
    if (x < 1 || y < 1 || x > n || y > m || vis[x][y] || c[x][y] == '#')
        return false;
    return true;
}

void dfs(int x, int y)
{
    if (c[n][m] == '#')
        return ;
    if (x == n && y == m)flag=1;
    if (flag)return ;
    for (int i = 0; i < 4; i++)
    {
        int xx = x + direc[i][0];
        int yy = y + direc[i][1];

        if (check(xx, yy))
        {
            vis[xx][yy] = 1;
            dfs(xx, yy);
            vis[xx][yy] = 0;

        }
    }

    return ;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> c[i][j];
        }
    }
    vis[1][1] = 1;
    dfs(1,1);
    if (flag)
    {
        cout << "Yes" << endl;
    }
    else
        cout << "No" << endl;
    return 0;
}

by coool @ 2023-08-30 12:25:24

@lujunxuan123 太久没写搜索dfs忘光了，已关注！

by coool @ 2023-08-30 12:25:35

@ryf20100124 已关注！

by coool @ 2023-08-30 12:25:46

此贴结