DFS（再帰関数）が正常に作動しない AtCoder Regular Contest 031-B 埋め立て

Question

ARC31-B(https://atcoder.jp/contests/arc031/tasks/arc031_2)でDFSを用いて実装したところ例１が作動しない。ほかの例は正常に作動。内部だと7(33中)がWA。どこが原因なのかわからないのでご教授願いたい。

• 方針

１．任意のスタートを〇から一つ決める
２．dfsの準備(×をTRUE、〇をFALSE）をしたものを２個用意（A、Bと名付ける）
３．Aを用いてdfs
４．３した時点でたどり着けなかったところ（FALSE)を記録
５．Bを用いてdfs（５では一度TRUEを進んでもOK）
６，４で記録した座標が５をしたらTRUEになったか調べる
７．６ですべてにおいてTRUEだったら”YES”

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,n) for(ll i=0;i<(n);++i)
#define pu(n) push_back(n)
#define INF 1000000000000 //10^12
/*-------------------------------------------------------------*/
vector<vector<bool>>g(10,vector<bool>(10,false));ll gx,gy;ll sx,sy;
vector<vector<bool>>G(10,vector<bool>(10,false));
vector<ll>dx={0,1,0,-1};vector<ll>dy={1,0,-1,0};
void dfs(ll a,ll b){// 3
    if(g[a][b])return;
    g[a][b]=true;
    rep(i,4){
        if(b==0 and i==2)continue;//全方位
        if(a==9 and i==1)continue;
        if(b==9 and i==0)continue;
        if(a==0 and i==3)continue;
        dfs(a+dx[i],b+dy[i]);
    }
}
void Dfs(ll a,ll b,ll cnt){//5
    if(G[a][b] and cnt>0)return;//一度までTRUE踏んでOKだよ～
    if(G[a][b])cnt++;　　　　　　//cntで何回TRUE踏んだか計測
    G[a][b]=true;
    rep(i,4){
        if(b==0 and i==2)continue;//全方位
        if(a==9 and i==1)continue;
        if(b==9 and i==0)continue;
        if(a==0 and i==3)continue;
        Dfs(a+dx[i],b+dy[i],cnt);
    }
}
int main(){
    rep(i,10){//入力
        rep(j,10){
            char c;cin>>c;
            if(c=='x'){g[i][j]=true;G[i][j]=true;}//2
            if(c=='o'){sx=i;sy=j;}                //1
        }
    }
   
    dfs(sx,sy);//3
    
    bool m=true;
    vector<ll>nx,ny;//4
    rep(i,10){
        rep(j,10){
            if(g[i][j]==false){
                m=false;
                nx.pu(i);ny.pu(j);
                
            }
        }
    }
    if(m){
        cout<<"YES"<<endl;return 0;//もしたどり着けなかったところなかったら
    }     
    
    Dfs(sx,sy,0);//5
    
    bool mi=true;
    rep(i,nx.size()){
        if(G[nx[i]][ny[i]]==false)mi=false;//6
    } 
    
    if(mi)cout<<"YES"<<endl;//7
    else cout<<"NO"<<endl;
    return 0;
}

---

一度これ↓を使って図に書きだしたが、どうやら全方位探索できてないようだった（例１）。

void Dfs(ll a,ll b,ll cnt){
    if(G[a][b] and cnt>0)return;
    if(G[a][b])cnt++;
    G[a][b]=true;
    /*rep(i,10){
        rep(j,10){
            if(i==a and j==b){
                cout<<'!';
            }
            if(G[i][j])cout<<'a';
            else cout<<'b';
        }cout<<endl;
    }cout<<endl;*/
    rep(i,4){
        if(b==0 and i==2)continue;
        if(a==9 and i==1)continue;
        if(b==9 and i==0)continue;
        if(a==0 and i==3)continue;
        Dfs(a+dx[i],b+dy[i],cnt);
    }
}

Answer 1

正直なところ、かなり大きな修正が必要になると思われます。
とりあえず、以下の入力でデバッグしてみてください(正しい出力はNO)。

xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxx
xxxxxxxxxo
xxxxxxxxxx
xxxxxxxoxo

Comments

[unknock]

actorbugさんのtextでこの解き方の問題点もわかりました。ありがとうございます！（dfsあまりやったことなくて・・・。でも一夜明けたら解き方思いつきました。）