60分dfs求调

zhaobingcheng @ 2023-08-20 14:16:30

#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[10010][1010];
int cx[5]={0,0,1,-1,0};
int cy[5]={1,-1,0,0,0};
bool vis[10010][10010];
int dfs(int x,int y){
    if(x==n&&y==m){
        return true;
    }
    if(a[x][y]=='.'&&vis[x][y]==0){
        vis[x][y]=1;
        for(int i=1;i<=4;i++){
            dfs(x+cx[i],y+cy[i]);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    if(dfs(1,1)){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}

by Delete_error @ 2023-08-20 14:48:40

第十五行加句判断是否越界，还有数组应该从0开始，不必考虑不走的情况

for(int i=0;i<4;i++){
    int tx=x+dx[i];
    int ty=y+dy[i];
    if(tx>=1&&tx<=n&&ty>=1&&ty<=m&&！(vis[tx][ty])&&maze[tx][ty]=='.'){
            dfs(tx,ty);
    }
}

by glx123 @ 2023-08-20 14:56:15

#include <bits/stdc++.h>
using namespace std;
int n,m;
char a[10010][1010];
int cx[5]={0,0,1,-1};
int cy[5]={1,-1,0,0};
bool vis[10010][10010];
bool p(int x,int y){
    return x>=1&&x<=n&&y>=1&&y<=m;//判是否越界 
}
void dfs(int x,int y){

    if(a[x][y]=='.'&&vis[x][y]==0){
        vis[x][y]=1;
        if(x==n&&y==m){//找到返回 
            return ;
        }    
        for(int i=0;i<4;i++){//下标从零开始 
            if(p(x+cx[i],y+cy[i]))
                dfs(x+cx[i],y+cy[i]);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    dfs(1,1);
    if(vis[n][m]){//判断是否来过 
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}

by Delete_error @ 2023-08-20 14:57:26

#include <bits/stdc++.h>
using namespace std;
int n,m,ok;
char a[10010][10010];
int cx[5]={0,0,1,-1};
int cy[5]={1,-1,0,0};
bool vis[10010][10010];
void dfs(int x,int y){
    if(x==n&&y==m){
        ok=true;
        return;
    }
    if(x>=1&&x<=n&&y>=1&&y<=m&&a[x][y]=='.'&&vis[x][y]==0){
        vis[x][y]=1;
        for(int i=0;i<4;i++){
            dfs(x+cx[i],y+cy[i]);
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    dfs(1,1);
    if(ok){
        cout<<"Yes";
    }
    else{
        cout<<"No";
    }
    return 0;
}

by glx123 @ 2023-08-20 14:57:35

之前函数可能没有返回值，会报错,给你改一下

by Delete_error @ 2023-08-20 14:59:51

@zhaobingcheng dfs应设为void类型进行调用

by Delete_error @ 2023-08-20 15:02:05

@glx123 功德++

by zhaobingcheng @ 2023-08-20 15:33:20

@aways 谢谢大佬

by zhaobingcheng @ 2023-08-20 15:38:22

@glx123 谢谢大佬