質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
多次元配列

1次元配列内にさらに配列を格納している配列を、多次元配列と呼びます。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

解決済

2次元配列を使った迷路探索(深さ優先探索)

kdt.nmk
kdt.nmk

総合スコア19

多次元配列

1次元配列内にさらに配列を格納している配列を、多次元配列と呼びます。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

1回答

0評価

0クリップ

315閲覧

投稿2022/01/27 01:18

[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

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

多次元配列

1次元配列内にさらに配列を格納している配列を、多次元配列と呼びます。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。