40分求助

Accelerator_5 @ 2022-12-05 13:10:11

#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
int mp[1005][1005];
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
bool vis[105][105]; 
void dfs(int x,int y){
    vis[x][y]=1;
    if(x>=m&&y>=n){
        return;
    } 
    for(int i=1;i<=4;i++){
        if(x+dx[i]>=1&&x+dx[i]<=m&&y+dy[i]>=1&&y+dy[i]<=n&&mp[x+dx[i]][y+dy[i]]!=1&&vis[x][y]==0){
            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++){
            char a;
            cin>>a;
            if(a=='#'){
                mp[i][j]=1;
            }
        }
    }
    dfs(1,1);
    if(vis[m][n]!=1){
        cout<<"No";
        return 0;
    }
    cout<<"Yes";
    return 0;
}

by mmh08100566 @ 2022-12-05 20:54:30

您对二维矩阵仍不够了解，需要加强一下呢

您的代码中，dfs里，判断下一个点能不能走的时候（20行），最后一个判断条件有误

应该是vis[x+dx[i]][y+dy[i]]，您写的是判断自己有没有走过，而您又在一开始就把自己标记了，所以您的深搜搜不出去。

第二：您的矩阵读入的时候是以n为行数，m为列数的，但是您的16行，20行，37行都与您的读入不一致，从而导致了错误

#include<iostream>
#include<cmath>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int n,m;
int mp[1005][1005];
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
bool vis[105][105]; 
void dfs(int x,int y){
    vis[x][y]=1;
    if(x>=n&&y>=m){
        return;
    } 
    for(int i=1;i<=4;i++){
        if(x+dx[i]>=1&&x+dx[i]<=n&&y+dy[i]>=1&&y+dy[i]<=m&&mp[x+dx[i]][y+dy[i]]!=1&&vis[x+dx[i]][y+dy[i]]==0){
            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++){
            char a;
            cin>>a;
            if(a=='#'){
                mp[i][j]=1;
            }
        }
    }
    dfs(1,1);
    if(vis[n][m]!=1){
        cout<<"No";
        return 0;
    }
    cout<<"Yes";
    return 0;
}

by mmh08100566 @ 2022-12-08 18:24:25

@Accelerator_5 难道我给您的代码对您没有任何帮助吗？

by Accelerator_5 @ 2022-12-09 13:10:06

@mmh08100566 谢谢谢谢，没看到消息