50pts 995!

B3625 迷宫寻路

E_RONALDO @ 2024-12-12 20:13:12

#include<bits/stdc++.h>
using namespace std;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
char mp[105][105];
bool vis[105][105];
int n,m;
bool f=0;
int cx=0,cy=0;
bool init(int xx,int yy){
    if(xx<1||xx>n||yy<1||yy>n){
        return 0;
    } 
    if(mp[xx][yy]=='#'||vis[xx][yy]==1){
        return 0;
    } 
    return 1;
}
void dfs(int x,int y){
    if(x==n&&y==m){
        cout<<"Yes";
        f=1;
        return;
    }

    for(int i=0;i<4;i++){
        cx=x+dx[i];
        cy=y+dy[i];
        if(init(cx,cy)){
            vis[cx][cy]=1;
            dfs(cx,cy);
        }

    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }
    dfs(1,1);
    if(f==0){
        cout<<"No";
    }

    return 0;
}

by yise @ 2024-12-12 20:22:05

@E_RONALDO 稍改了一下

#include<bits/stdc++.h>
using namespace std;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
char mp[105][105];
bool vis[105][105];
int n,m;
bool init(int xx,int yy){
    if(xx<1||xx>n||yy<1||yy>m){
        return 0;
    } 
    if(mp[xx][yy]=='#'||vis[xx][yy]==1){
        return 0;
    } 
    return 1;
}
void dfs(int x,int y){
    if(!init(x,y)) return;
    if(x==n&&y==m){
        cout<<"Yes";
        exit(0);
    }
    vis[x][y]=1;
    for(int i=0;i<4;i++){
        dfs(x+dx[i],y+dy[i]);
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>mp[i][j];
        }
    }
    dfs(1,1);
    cout<<"No";
    return 0;
}

|