前提
再帰関数を用いた全探索で、問題を解きたいと考えていますが、うまく機能しません。
陸がつながっているということを判定するには、どのようなことを実装すればいいでしょうか。
(問題)
・島国の地図が 10 行にわたって与えられる。
・各行は 10 文字からなり、o は陸地を、x は海を表す。
・少なくとも 1 マスは陸地があることが保証される。
・少なくとも 1 マスは海があることが保証される。
・海を 1 マスだけ陸地にすることで全体を 1 つの島にできるなら YES 、できないなら NO を出力せよ。出力の末尾には改行をつけること。ただし、元から 1 つの島だった場合も YES を出力せよ。
実現したいこと
・まず何もしていない一番初めの状態の陸の数を数える
・海の一つを陸に変えて、全探索を用いて、陸から陸に行けたらsumを+1する
・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/ツールのバージョンなど)
ここにより詳細な情報を記載してください。


回答1件
あなたの回答
tips
プレビュー