60分求调

B3625 迷宫寻路

dsh2013_1 @ 2024-10-08 19:53:03

代码

#include <bits/stdc++.h>
using namespace std;
int n,m,f=0,b[105][105],cnt[105][105];
void dfs(int x,int y){
    if(f==1) return;
    if(x==n&&y==m){
        cout<<"Yes";
        f=1;
        return;
    }
    if(x==n&&cnt[x-1][y]==1&&cnt[x][y-1]==1&&cnt[x][y+1]==1||y==m&&cnt[x-1][y]==1&&cnt[x][y-1]==1&&cnt[x+1][y]==1||cnt[x+1][y]==1&&cnt[x][y+1]==1&&cnt[x-1][y]==1&&cnt[x][y-1]==1)
        return;
        if(x!=1&&cnt[x-1][y]==0&&b[x-1][y]!='#'){
            cnt[x-1][y]=1;
            dfs(x-1,y);
            cnt[x-1][y]=0;
        }
        if(y!=1&&cnt[x][y-1]==0&&b[x][y-1]!='#'){
            cnt[x][y-1]=1;
            dfs(x,y-1);
            cnt[x][y-1]=0;
        }
        if(x!=n&&cnt[x+1][y]==0&&b[x+1][y]!='#'){
            cnt[x+1][y]=1;
            dfs(x+1,y);
            cnt[x+1][y]=0;
        }
        if(y!=m&&cnt[x][y+1]==0&&b[x][y+1]!='#'){
            cnt[x][y+1]=1;
            dfs(x,y+1);
            cnt[x][y+1]=0;
        }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>b[i][j];
            if(b[i][j]=='#') cnt[i][j]=1;
        }
    }
            if(b[n][m]=='#'||b[n-1][m]=='#'&&b[n][m-1]=='#'){
                cout<<"No";
                return 0;
            }
    dfs(1,1);
    if(f==0) cout<<"No";
    return 0;
}

by Lisuyang @ 2024-10-08 20:08:12

极品dfs

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

by Lisuyang @ 2024-10-08 20:08:24

@dsh2013_1

by dsh2013_1 @ 2024-10-08 20:56:10

@lisuyang 已关注

|