深さ優先探索を用いた問題の解決

Question

前提

再帰関数を用いた全探索で、問題を解きたいと考えていますが、うまく機能しません。
陸がつながっているということを判定するには、どのようなことを実装すればいいでしょうか。

（問題）
・島国の地図が 10 行にわたって与えられる。
・各行は 10 文字からなり、o は陸地を、x は海を表す。
・少なくとも 1 マスは陸地があることが保証される。
・少なくとも 1 マスは海があることが保証される。
・海を 1 マスだけ陸地にすることで全体を 1 つの島にできるなら YES 、できないなら NO を出力せよ。出力の末尾には改行をつけること。ただし、元から 1 つの島だった場合も YES を出力せよ。

実現したいこと

・まず何もしていない一番初めの状態の陸の数を数える
・海の一つを陸に変えて、全探索を用いて、陸から陸に行けたらsumを＋１する
・sumと最初に数えた陸の数が同じなら、yesを出力する

発生している問題・エラーメッセージ

・陸がつながっているかいないかに関わらず、全ての場合においてyesを出力してしまう

該当のソースコード

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>
using namespace std;

const int h = 10;
const int w = 10;
vector<vector<char>> v(h,vector<char>(w));
vector<vector<bool>> judge(h,vector<bool>(w));
bool ans = false;
int sum = 1;
int counter = 0;

void field_search(int x, int y) {
    //陸を探索する
    //探索範囲を限定する
    if(x < 0 || y < 0 || x > h - 1 || y > w - 1 || v[x][y] == 'x')
        return;
    if(v[x][y])
    //一度来たことあるか判定する
    if(judge[x][y] == true)
        return;
    //来た場所にフラグを立てる
    judge[x][y] = true;
    //探索する
    field_search(x, y + 1);
    field_search(x, y - 1);
    field_search(x + 1, y);
    field_search(x - 1, y);
}

void sea_search(int x, int y) {
    //海の一つを陸に変える
    if(v[x][y] == 'x') {
        v[x][y] = 'o';
        //陸を探索していって、全てを通ることができたら成功
        field_search(x, y);
    }
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(judge[i][j] == true)
                sum++;
        }
    }
    if(sum == counter)
        ans = true;
    else {
        v[x][y] = 'x';
        sum = 0;
    }
    
}

int main() {
    //入力
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            cin >> v[i][j];
        }
    }
    //陸の数を数える
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(v[i][j] == 'o')
                counter++;
        }
    }
    //すべての海からスタートする
    for(int i = 0; i < h; i++) {
        for(int j = 0; j < w; j++) {
            if(v[i][j] == 'x')
                sea_search(i,j);
            if(ans)
                break;
        }
        if(ans)
            break;
    }
    
    if(ans)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    
}

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[actorbug]

問題のURLを載せてください。
現状、入力例・出力例が無いので、動作確認が難しいです。

[nisi]

https://atcoder.jp/contests/arc031/tasks/arc031_2

こちらです。お願いします。

[Zuishin]

マスの数が少ないので、力技でできます。
まず陸のマスを数えます。
次に海のマスを一つ選び、そこから地続きの陸を深さ優先探索し、地続きのマスが予め数えた陸のマスと同じ数になった時、そこを埋め立てれば一つの島になります。

[退会済みユーザー]

そもそも海にしたのに陸かどうかを判定しに行ったり、判定を何度も使ってるのに誰も元に戻そうとしてなかったり、いろいろおかしいけど、そもそもatcoderの問題を題材にした質問は個人的にあまり推奨したくないですね。バグ探しとか回答依頼というのはちょっと。。。

[fana]

(1)ラベリング処理を実施する→陸の個数Nがわかる．
(2)隣接する陸マスのラベル種類がN種類になる海マスがあるかどうか

でやれるように思う．

Answer 1

問題点が2つあります。

1つ目は、sum == counterで判定していることです。
海の一つを陸に変えているのだから、sumはcounter(最初に数えた陸の数)より1つ多いはずです。

2つ目は、海を陸に変えるたびにjudgeをリセットしていないことです。
入力例2で、左上を海から陸にした後、judgeは以下の状態になります(Fがfalse、Tがtrue)

TFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF

次に、その右隣りの海を陸にするわけですが、jugdeは前回修正した内容がそのまま残るため、以下のようになります。

TTFFFFFFFF
FTTTTTTTFF
FFTTTTTFFF
FFFTTTFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF
FFFFFFFFFF

これを繰り返すと、左上から1つずつTが増えていくことになり、いずれ最初に数えた陸の数と等しくなってYESを出力してしまうことになります。

Comments

[nisi]

ありがとうございます！
もう一回見直してみたいと思います！