求助！不会宽搜，深搜只有50分！

jinhaoyu142857 @ 2024-02-22 18:33:04

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool _map[200][200],flag,feet[200][200];
void dfs(int x,int y){
    if(x>n||y>m||x==0||y==0||_map[x][y]==1){
        return ;
    }
    if(x==n&&y==m){
        flag=1;
        return ;
    }
    if(flag)return ;
    if(feet[x+1][y]==0){
        feet[x+1][y]=1;
        dfs(x+1,y);
        feet[x+1][y]=0;
    }
    if(flag)return ;
    if(feet[x-1][y]==0){
        feet[x-1][y]=1;
        dfs(x-1,y);
        feet[x-1][y]=0;
    }
    if(flag)return ;
    if(feet[x][y+1]==0){
        feet[x][y+1]=1;
        dfs(x,y+1);
        feet[x][y+1]=0;
    }
    if(flag)return ;
    if(feet[x][y-1]==0){
        feet[x][y-1]=1;
        dfs(x,y-1);
        feet[x][y-1]=0;
    }
    if(flag)return ;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s;
            cin>>s;
            if(s=='.')_map[i][j]=0;
            else _map[i][j]=1;
        }
    }
    feet[1][1]=1;
    dfs(1,1);
    if(flag)cout<<"Yes";
    else cout<<"No";
}

by linch @ 2024-02-22 18:40:35

这题不需要回溯。 @jinhaoyu142857

by linch @ 2024-02-22 18:42:06

@jinhaoyu142857 这几句回溯注释掉就 A 了。

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool _map[200][200],flag,feet[200][200];
void dfs(int x,int y){
    if(x>n||y>m||x==0||y==0||_map[x][y]==1){
        return ;
    }
    if(x==n&&y==m){
        flag=1;
        return ;
    }
    if(flag)return ;
    if(feet[x+1][y]==0){
        feet[x+1][y]=1;
        dfs(x+1,y);
        //feet[x+1][y]=0;
    }
    if(flag)return ;
    if(feet[x-1][y]==0){
        feet[x-1][y]=1;
        dfs(x-1,y);
        //feet[x-1][y]=0;
    }
    if(flag)return ;
    if(feet[x][y+1]==0){
        feet[x][y+1]=1;
        dfs(x,y+1);
        //feet[x][y+1]=0;
    }
    if(flag)return ;
    if(feet[x][y-1]==0){
        feet[x][y-1]=1;
        dfs(x,y-1);
        //feet[x][y-1]=0;
    }
    if(flag)return ;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s;
            cin>>s;
            if(s=='.')_map[i][j]=0;
            else _map[i][j]=1;
        }
    }
    feet[1][1]=1;
    dfs(1,1);
    if(flag)cout<<"Yes";
    else cout<<"No";
}

评测记录

by _qingshu_ @ 2024-02-22 18:42:10

@jinhaoyu142857

#include<bits/stdc++.h>
using namespace std;
int n,m;
bool _map[200][200],flag,feet[200][200];
void dfs(int x,int y){
    if(x>n||y>m||x==0||y==0||_map[x][y]==1){
        return ;
    }
    if(x==n&&y==m){
        flag=1;
        return ;
    }
    if(flag)return;
    if(feet[x+1][y]==0){
        feet[x+1][y]=1;
        dfs(x+1,y);
    }
    if(flag)return ;
    if(feet[x-1][y]==0){
        feet[x-1][y]=1;
        dfs(x-1,y);
    }
    if(flag)return ;
    if(feet[x][y+1]==0){
        feet[x][y+1]=1;
        dfs(x,y+1);
    }
    if(flag)return ;
    if(feet[x][y-1]==0){
        feet[x][y-1]=1;
        dfs(x,y-1);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            char s;
            cin>>s;
            if(s=='.')_map[i][j]=0;
            else _map[i][j]=1;
        }
    }
    feet[1][1]=1;
    dfs(1,1);
    if(flag)cout<<"Yes";
    else cout<<"No";
}

by _qingshu_ @ 2024-02-22 18:44:55

@jinhaoyu142857

显而易见的，回溯的话你的复杂度会从 \mathcal{O}(N\times M) 变成一个指数级别的东西。

by jinhaoyu142857 @ 2024-02-22 18:54:51

@linch Thank you!!!^_^