wangsijie0820 @ 2023-09-28 20:11:54

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

int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}},flag;
char a[105][105],n,m;
void dfs(int x,int y) {
    if (x == n && y == m) {
        cout << "Yes";
        exit(0);
    }

    for (int i = 0;i < 4;i++) {
        int nx = x + d[i][0],ny = y + d[i][1];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == '.') {
            a[nx][ny] = '#';
            dfs(nx,ny);
        }
    }
}

int main(){
    cin >> n >> m;
    memset(a,'#',sizeof(a));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
        }
    }

    dfs(1,1);

    if (!flag) cout << "No";
    else cout << "Yes";
    return 0;
}

by wangsijie0820 @ 2023-09-28 20:14:08

更新，还是过不了

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

int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}},flag;
char a[105][105],n,m;
void dfs(int x,int y) {
    if (x == n && y == m) {
        cout << "Yes";
        exit(0);
    }

    for (int i = 0;i < 4;i++) {
        int nx = x + d[i][0],ny = y + d[i][1];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == '.') {
            a[nx][ny] = '#';
            dfs(nx,ny);
        }
    }
}

int main(){
    cin >> n >> m;
    memset(a,'#',sizeof(a));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
        }
    }

    dfs(1,1);

    cout << "No";

    return 0;
}

by Willson1307 @ 2023-09-28 20:19:19

• 要回溯，dfs(nx,ny)后加上a[nx][ny] = '.'
• dfs 前加上 a[1][1] = '#'（不能重复走到起点）

by craftmine @ 2023-09-30 11:55:01

你这里有搜索，为什么没有回溯？ 要状态恢复，不然会卡死。

@Willson1307 后面的好像不用吧（可以走回起点）。

by wangsijie0820 @ 2023-09-30 17:21:11

加了回溯过不了

https://www.luogu.com.cn/record/126720936

10 TLE #7 WA

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

int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}},flag;
char a[105][105],n,m;
void dfs(int x,int y) {
    if (x == n && y == m) {
        cout << "Yes";
        exit(0);
    }

    for (int i = 0;i < 4;i++) {
        int nx = x + d[i][0],ny = y + d[i][1];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == '.') {
            a[nx][ny] = '#';
            dfs(nx,ny);
            a[nx][ny] = '.';  // 回溯在这里
        }
    }
}

int main(){
    cin >> n >> m;
    memset(a,'#',sizeof(a));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
        }
    }

    dfs(1,1);

    cout << "No";

    return 0;
}

by hzy99999 @ 2023-10-06 09:02:17

@oliverwang2013 你写成char n,m;了

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

int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}},flag;
char a[105][105];
int n,m;
void dfs(int x,int y) {
    if (x == n && y == m) {
        cout << "Yes";
        exit(0);
    }

    for (int i = 0;i < 4;i++) {
        int nx = x + d[i][0],ny = y + d[i][1];
        if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && a[nx][ny] == '.') {
            a[nx][ny] = '#';
            dfs(nx,ny);
        }
    }
}

int main(){
    cin >> n >> m;
    memset(a,'#',sizeof(a));
    for (int i = 1;i <= n;i++) {
        for (int j = 1;j <= m;j++) {
            cin >> a[i][j];
        }
    }

    dfs(1,1);

    cout << "No";

    return 0;
}

by wangsijie0820 @ 2023-10-06 18:43:06

...

by wangsijie0820 @ 2023-10-06 18:46:34

@hzy99999 谢谢，AC