全T求条

hiebb @ 2024-08-14 18:30:11

#include<bits/stdc++.h>
using namespace std;
int n,m;
char c;
bool f[110][110],ff=1;
void dfs(int x,int y){
    if(x<0||y<0||x>n||y>m||f[x][y]) return;
    if(x==n&&y==m){
        ff=0;
        cout<<"YES";
        return;
    }
    f[x][y]=1;
    if(!f[x-1][y]&&ff) dfs(x-1,y);
    if(!f[x+1][y]&&ff) dfs(x+1,y);
    if(!f[x][y-1]&&ff) dfs(x,y-1);
    if(!f[x][y+1]&&ff) dfs(x,y+1);
    f[x][y]=0;
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            cin>>c;
            if(c=='#') f[i][j]=1;
            else f[i][j]=0;
        }
    dfs(1,1);
    if(ff) cout<<"NO";
    return 0;
}

by Gzh320667 @ 2024-08-14 18:34:41

1≤n,m≤100要广搜

by shtian @ 2024-08-14 18:38:26

@Gzh320667 无需广搜，dfs水淹也可以过

by hiebb @ 2024-08-14 18:38:47

QwQ还没学，学了再来吧

by shtian @ 2024-08-14 18:40:44

@hiebb 你的代码有多个错误

1. dfs不用回溯
2. yes，no的大小写
3. dfs中

   if(!f[x-1][y]&&ff) dfs(x-1,y);
   if(!f[x+1][y]&&ff) dfs(x+1,y);
   if(!f[x][y-1]&&ff) dfs(x,y-1);
   if(!f[x][y+1]&&ff) dfs(x,y+1);

   f的访问会爆

by hiebb @ 2024-08-14 18:45:12

哦~

by hiebb @ 2024-08-14 18:47:46

改完之后A了一个，但其他的还是T

by Adorable_ @ 2024-09-25 19:00:42

@shtian 大佬可以说一下为什么不用回溯吗

by shtian @ 2024-09-27 12:35:25

@Adorable_ 此题之要求算是否可以到达

#include <bits/stdc++.h>
using namespace std;
int n, m;
bool vis[105][105];//是否已经走过或是墙
char a[105][105];
int u;

void dfs(int x, int y) {
    if (x < 1 || x > n || y < 1 || y > m || a[x][y] == '#' || vis[x][y] == 1) {
        return;
    }
    if (x == n && y == m) {
        u++;//标记可以到终点
        return;
    }
    vis[x][y] = 1;//压在一个数组里
    dfs(x + 1, y);//这些可以到
    dfs(x - 1, y);
    dfs(x, y + 1);
    dfs(x, y - 1);
}

int main() {
    cin >> n >> m ;
    for (int j = 1; j <= n; j++) {
        for (int i = 1; i <= m; i++) {
            cin >> a[j][i];
        }
    }
    dfs(1, 1);
    if (u == 0) {
        cout << "No";
    } else {
        cout << "Yes";
    }
    return 0;
}

by shtian @ 2024-09-27 12:36:54

@Gzh320667

by shtian @ 2024-09-27 12:39:03

4行注释错了，是

bool vis[105][105];//是否已经走过（到达）

vis[x][y] = 1;//走过了（可以到达）