[A - 深さ優先探索] https://atcoder.jp/contests/atc001/tasks/dfs_a
この問題を解きたいと思い、下記のコードを書きました。
現在位置の上には進めるのですが、それ以外の方向に思ったように進みません。
配列の範囲についてエラーが出ているので、それと関係あると思うのですが、根本原因が分かりません。
デバッグをして、if文のあたりが怪しいような気がしています。
深さ優先探索の仕組みについては、概ね理解しているつもりです。
よろしくお願いします。
c++
#include <bits/stdc++.h> using namespace std; bool find (int H, int W, vector<vector<char>> map, vector<vector<int>> stack, int a, int b) { //現在地がgになったらtrue、終了 if(map.at(a).at(b) == 'g') { cout<<"goal"<<endl; return true; } stack.push_back({a,b}); map.at(a).at(b)='o'; cout<<endl; cout<<"------------------"<<endl; cout << a<<","<<b<<endl; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { cout<< map.at(i).at(j); } cout << endl; } //進めるなら進む if((map.at(a-1).at(b)=='.' || map.at(a-1).at(b)=='g') && 0 <= a-1 && a-1 < H && 0 <= b && b < W) { cout << "上"<< endl; a-=1; return find (H, W, map, stack, a, b); } else if ((map.at(a+1).at(b)=='.' || map.at(a+1).at(b)=='g') && 0 <= a+1 && a+1 < H && 0 <= b && b < W) { cout << map.at(a+1).at(b) <<endl; cout << "下"<< endl; a+=1; find (H, W, map, stack, a, b); } else if ((map.at(a).at(b-1)=='.' || map.at(a).at(b-1)=='g') && 0 <= a && a < H && 0 <= b-1 && b-1 < W) { cout << "左"<<endl; b-=1; find (H, W, map, stack, a, b); } else if ((map.at(a).at(b+1)=='.' || map.at(a).at(b+1)=='g') && 0 <= a && a < H && 0 <= b+1 && b+1 < W) { cout << "右"<<endl; b+=1; find (H, W, map, stack, a, b); } //四方行けなかったら、道が出てくるまで1マスずつ戻る else { cout << "行き止まり"<<endl; while (map.at(a-1).at(b)=='.' || map.at(a+1).at(b)=='.' || map.at(a).at(b-1)=='.' || map.at(a).at(b+1)=='.' || map.at(a-1).at(b)=='g' || map.at(a+1).at(b)=='g' || map.at(a).at(b-1)=='g' || map.at(a).at(b+1)=='g') { int i = 2; a=stack.at(stack.size()-i).at(0); b=stack.at(stack.size()-i).at(1); i++; //スタートを通過しても行ける場所が無かったら終了 if (i>stack.size()+10) { return false; } find (H, W, map, stack, a, b); } } } int main() { int H, W; cin >> H >> W; //迷路入力 vector<vector<char>> map(H, vector<char>(W)); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { cin >> map.at(i).at(j); } } //スタート地点確認 int a, b; for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { if (map.at(i).at(j) == 's') { a=i; b=j; } } } vector<vector<int>> stack(0, vector<int>(0)); bool result = find(H,W,map,stack,a,b); cout << result << endl; }
input
4 3 s.. .## ... g..
エラーメッセージ
[Wandbox] Start
prog.cc: In function 'bool find(int, int, std::__debug::vector<std::__debug::vector<char> >, std::__debug::vector<std::__debug::vector<int> >, int, int)':
prog.cc:72:1: warning: control reaches end of non-void function [-Wreturn-type]
72 | }
| ^
引用テキスト
terminate called after throwing an instance of 'std::out_of_range'
what(): vector::_M_range_check: __n (which is 4) >= this->size() (which is 4)
[Signal] Aborted
[Wandbox] Finish
まだ回答がついていません
会員登録して回答してみよう