C++再帰関数 行ってほしい地点に行ってくれない
解決したいこと
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
この図の赤く囲われたところから再帰関数がスタートし、上の陸地だけしか行われていないことが分かります。下も含めて探索してほしいんですが、何が間違っているのでしょうか。
0