求助P1746

P1746 离开中山路

LiJingone_Andy @ 2022-07-14 14:41:52

我用的DFS,但不知道那里错了,答案不对,求改正

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#define QWQ puts("QWQ");
#define ll long long
#define MAXN 100010
using namespace std;
ll n,ha,la,hb,lb,j,ans[10000];
string a[200];
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
void dfs(int idx,int idy){
    j++;
    for(int i=0;i<4;i++){
        int x=idx+dx[i];
        int y=idy+dy[i];
        if(x<=0||x>n||y<=0||y>n||a[x][y]=='2'||a[x][y]=='1')continue;
        if(a[x][y]=='0'){
            ans[j]++;
            a[x][y]='2';
            dfs(x,y);
        }
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cin>>ha>>la>>hb>>lb;
    a[ha][la]='2';
    dfs(ha,la);
    sort(ans,ans+j);
    cout<<ans[1];
    return 0;
}

by 晴空一鹤 @ 2022-07-14 14:48:14

其实

我想问个问题

hb和lb你都没用啊


by 晴空一鹤 @ 2022-07-14 14:48:31

@李敬one


by LiJingone_Andy @ 2022-07-14 15:17:49

@晴空一鹤 你是说写个出口?


by 晴空一鹤 @ 2022-07-14 15:43:23

ng


by LiJingone_Andy @ 2022-07-14 15:58:12

@晴空一鹤 可以帮忙改一下吗


by 晴空一鹤 @ 2022-07-14 16:04:30

这题建议用BFS吧

DFS时间复杂度会起飞

另外正确性很难保证

@李敬one


by LiJingone_Andy @ 2022-07-14 16:28:01

@晴空一鹤 好吧


by LiJingone_Andy @ 2022-07-14 16:28:21

@晴空一鹤 非常感谢


|