0pts
查看原帖
0pts
1085701
zzgj1235楼主2025/1/11 11:48
#include<bits/stdc++.h>
using namespace std;
char a[120][80];
int n,m,dp[120][80];
void dfs(int x,int y,int z){
    if(dp[x][y]<=z||x>n||x<1||y>m||y<1||a[x][y]=='#'){
        return;
    }
    dp[x][y]=z;
    dfs(x+1,y,z+1);
    dfs(x-1,y,z+1);
    dfs(x,y+1,z+1);
    dfs(x,y-1,z+1);
}
void dfc(int x,int y){
    cout<<x<<" "<<y<<endl;
    if(x==n&&y==m){
        return;
    }
    if(min(dp[x+1][y],min(dp[x-1][y],min(dp[x][y-1],dp[x][y+1])))==dp[x+1][y]){
        dfc(x+1,y);
    }
    if(min(dp[x+1][y],min(dp[x-1][y],min(dp[x][y-1],dp[x][y+1])))==dp[x-1][y]){
        dfc(x-1,y);
    }
    if(min(dp[x+1][y],min(dp[x-1][y],min(dp[x][y-1],dp[x][y+1])))==dp[x][y-1]){
        dfc(x,y-1);
    }
    if(min(dp[x+1][y],min(dp[x-1][y],min(dp[x][y-1],dp[x][y+1])))==dp[x][y+1]){
        dfc(x,y+1);
    }
}
int main(){
    memset(dp,100,sizeof(dp));
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
        }
    }
    dfs(n,m,0);
    dfc(1,1);
    return 0;
}
2025/1/11 11:48
加载中...