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

Question

[A - 深さ優先探索] https://atcoder.jp/contests/atc001/tasks/dfs_a

　この問題を解きたいと思い、下記のコードを書きました。
現在位置の上には進めるのですが、それ以外の方向に思ったように進みません。
配列の範囲についてエラーが出ているので、それと関係あると思うのですが、根本原因が分かりません。
デバッグをして、if文のあたりが怪しいような気がしています。
深さ優先探索の仕組みについては、概ね理解しているつもりです。
よろしくお願いします。

#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;
}

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

Answer 1

if((map.at(a-1).at(b)=='.' || map.at(a-1).at(b)=='g') && 0 <= a-1 && a-1 < H && 0 <= b && b < W)

これ系の箇所，
ショートサーキットを想定しているのであれば，範囲チェックを先に書く必要があります．

if(
  0 <= a-1 && a-1 < H && 0 <= b && b < W  //範囲チェックを先に
  && (map.at(a-1).at(b)=='.' || map.at(a-1).at(b)=='g')  //mapへのアクセスを後に
)

---

[追記]
それはそれとして，
find() は再帰として実装しつつも stack とかいう謎の履歴データ(?)っぽいのがあったりして，考えが整理されてない感．
再帰でやるならこのくらい↓の話になるのでは？

bool find( int H, int W, std::vector< std::vector<char> > &map, int x, int y )
{
	if( x<0 || y<0 || W<=x || H<=y )return false;
	
	char &attr = map[y][x];
	if( attr=='#' || attr=='o' )return false;

	std::cout << x << ", " << y << std::endl;	//output for debug
	if( attr=='g' )return true;
	attr = 'o';

	return ( find(H,W,map,x,y-1) || find(H,W,map,x-1,y) || find(H,W,map,x+1,y) || find(H,W,map,x,y+1) );
}

int main()
{
	//※入力部とかは面倒なので省略※
	std::vector< std::vector<char> > map
	{
		{ 's', '.', '.' },
		{ '.', '#', '#' },
		{ '.', '.', '.' },
		{ 'g', '.', '.' }
	};
	std::cout << ( find( 4,3,map,0,0 ) ? "Yes" : "No" ) << std::endl;
	return 0;
}

Comments

[kdt.nmk]

質問への回答、及び追記ありがとうございます。
追記について、returnの仕方に膝を打ちました。
returnで演算子を使える事を知らず（そしてそのような発想が全く無く）、冗長なコードになっていました。

return で or を使って、「4方向の内、壁が無い方向(true)を返す」 + 「それを総当たりで繰り返して、最終的にtrueになる組み合わせを見つけてくる」という理解で正しいでしょうか。

[kdt.nmk]

（記録として書かせていただきます。）
質問で上げたコードは、if を使って、わざわざ進む方向を1マス1マス決定しようとする考え方をしています。
そうすると、「進んだ先が袋小路になっている → 来た道を戻る」という手順が必要になるため、stack で道順を記録し、それを使って、来た道を分岐点まで戻るという操作をしようとしたため、変数に道順の履歴を入れるための配列が入っています。
総当たりで判断できるのであれば、そのような手順は必要ないです。

[fana]

> return ( find(H,W,map,x,y-1) || find(H,W,map,x-1,y) || find(H,W,map,x+1,y) || find(H,W,map,x,y+1) );

は，単に

if( find(H,W,map,x,y-1) )return true;
if( find(H,W,map,x-1,y) )return true;
if( find(H,W,map,x+1,y) )return true;
if( find(H,W,map,x,y+1) )return true;
return false;

を１行で書いたというだけです．

[fana]

> 来た道を分岐点まで戻るという操作

再帰的に呼びされている find() というのは，「１個手前のマスを調べた find()」 から呼ばれているわけですから，
来た道を１個戻るには単に return false; とすれば良いです．
「現在までの呼び出しの羅列＝履歴」なわけですから別途履歴を保持する必要はありません．