shin3110
@shin3110

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

C++再帰関数 行ってほしい地点に行ってくれない

Q&A

Closed

解決したいこと

C++でARC031のB-埋め立てという問題を解こうとしているんですが、下にあるコードだと行きたい地点に行けていないことが分かります。その原因と解決方法を教えてほしいです。エラーはありません。
また、探索する範囲が上下左右だけじゃなくて周りの8マス全て探索するため問題と違う部分がありますが、そこは後で直します。

該当するソースコード

#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)

void dfs(int i, int j, vector<vector<bool>> &pop, vector<vector<char>> a) {
    pop.at(i).at(j) = true;
    rep2(x, -1, 2) {
        rep2(y, -1, 2) {
            if (i+x < 10 && i+x >= 0 && j+y < 10 && j+y >= 0) {
                if (!pop.at(i+x).at(j+y)) {
                    if (a.at(i+x).at(j+y) == 'o') {
                        cout << i+x << ' ' << j+y << endl; //どこの地点にいるのかを知るために追加
                        dfs(i+x, j+y, pop, a);
                    }
                }
            }
        }
    }
}

int main() {
    vector<vector<char>> a(10, vector<char>(10));
    rep(i, 10) {
        rep(j, 10) {
            cin >> a.at(i).at(j);
        }
    }
    int cnt = 1;
    rep(i, 10) {
        rep(j, 10) {
            if (a.at(i).at(j) == 'o') {
                cnt++;
            }
        }
    }
    rep(i, 10) {
        rep(j, 10) {
            if (/*a.at(i).at(j) == 'x'*/i == 4 && j == 3) {//サンプルの解答は分かっていたので正解の地点だけ実行しています
                vector<vector<bool>> pop(10, vector<bool>(10, false));
                dfs(i, j, pop, a);
                int ans = 0;
                rep(m, 10) {
                    rep(n, 10) {
                        if (pop.at(m).at(n)) {
                            ans++;
                        }
                    }
                }
                cout << ans << endl; //追加した一つの地点とそこから行ける陸地の数
                if (ans == cnt) {
                    cout << "YES" << endl;
                    exit(0);
                }
            }
        }
    }
    cout << "NO" << endl;
}

サンプルの入力例

xxxxxxxxxx
xoooooooxx
xxoooooxxx
xxxoooxxxx
xxxxoxxxxx
xxxxxxxxxx
xxxxoxxxxx
xxxoooxxxx
xxoooooxxx
xxxxxxxxxx

上のコードの実行結果(実際はYESかNOで答える))

//繋がっていると判定された陸地の座標
//もっとあるはず
3 3 
2 2
1 1
1 2
1 3
1 4
1 5
1 6
1 7
2 6
2 5
2 4
2 3
3 4
3 5
4 4
17 //本当は26になってほしい
NO

ARC031-B.png

この図の赤く囲われたところから再帰関数がスタートし、上の陸地だけしか行われていないことが分かります。下も含めて探索してほしいんですが、何が間違っているのでしょうか。

0

1Answer

if (/*a.at(i).at(j) == 'x'*/i == 4 && j == 3) {//サンプルの解答は分かっていたので正解の地点だけ実行しています

検証はしていませんが、
正解の位置は、i == 5 && j == 4 では?

1Like

Your answer might help someone💌