全探索について ～スタックオーバーフローこわいけど大丈夫！～
この記事は突っ込みどころがおそらく満載でお送りしますので間違ってたら是非突っ込んでください
立命館合宿中に、
再帰によるスタックオーバーフローで数回WAをもらいました。
全探索（深さ優先探索）は再帰で書くのが楽ですが、
スタックオーバーフローが起こりうるので
他の手段による全探索を書ける必要があります。
今回はAOJ1130 Red and Black を対象としてコードを作成します
・ICPC Domestic 2004 B
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1130
長すぎるんで大雑把に説明します
- 再帰関数の引数をメンバに持つ構造体を作る
- 作った構造体を保持できるstackを再帰関数に突っ込む
- stackがからになるまでのループを書く（この中に再帰関数の処理部分を突っ込む）
- ループの前にstackに初期状態を突っ込む
- ループの最初にstackから状態を取り出す処理を書く
- 再帰を呼び出していた部分でstackに突っ込む処理に変える
長すぎる本編
まず、main関数を書きます
int w,h;
string map[40];
int main(){
while(cin>>w>>h,w){
int fx,fy;
for(int i=0;i<h;i++){
cin>>map[i];
}
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(map[i][j]=='@'){
fx=i;
fy=j;
break;
}
}
}
int ans=solve(fx,fy);
cout<<ans<<endl;
}
}はい、書きました。
必要なデータは
mapと初期位置です。
solve関数に初期位置を渡したら、
答えが帰ってきて欲しい感じになりました。
solve関数を書きます
int vec[4][2]={{0,1},{0,-1},{-1,0},{1,0}};
int solve(int x,int y){
int ans=1;
map[x][y]='#';
for(int i=0;i<4;i++){
if((x+vec[i][0]>=0)&&(y+vec[i][1]>=0)&&(x+vec[i][0]<h)&&(y+vec[i][1]<w)){
if(map[x+vec[i][0]][y+vec[i][1]]=='.'){
ans+=solve(x+vec[i][0],y+vec[i][1]);
}
}
}
return ans;
}vecはn回目に移動する時の移動方向のベクトルですね。
経路探索で辺が与えられる時とかは、vec→edgeみたいに読み替えましょう。
時々配列外参照とかをしてしまうので、
if((x+vec[i][0]>=0)&&(y+vec[i][1]>=0)&&(x+vec[i][0]<h)&&(y+vec[i][1]<w))
この部分でそれを防止して
if(map[x+vec[i][0]][y+vec[i][1]]=='.')
これで移動先に道があるかを確認して
再帰で呼び出します
なんてことはない深さ優先探索ですね。
（この問題ではまったく問題ないけれど）
呼び出し回数によってはこれでスタックオーバーフローを起こします
＊ここからはこの問題でオーバーフローを起こしたと仮定します
もう一回solve関数を一から書き直すのはめんどくさい上に時間もかかります（コンテスト中ならなおさら）
よって、今書いたsolve関数を利用して書いていきます
今書いたsolve関数は
int solve(int x,int y){
//自分の位置のタイルの数を足す
int ans=1;
//移動できるところに移動して
//移動先以降のタイルの枚数を足す
for(int i=0;i<4;i++){
//ここから二行条件判定
if((x+vec[i][0]>=0)&&(y+vec[i][1]>=0)&&(x+vec[i][0]<h)&&(y+vec[i][1]<w)){
if(map[x+vec[i][0]][y+vec[i][1]]=='.'){
//動いたタイルを調査済みにする
map[x][y]='#';
ans+=solve(x+vec[i][0],y+vec[i][1]);
}
}
}
return ans;
}というふうになっています。
再帰を使わずに深さ優先探索を行う場合、
stackというデータ構造を使用します
stackとは、机の上に積み上がっていく本のようなデータ構造です
※説明がだるいのでWikipediaを参照してください
stackでどうして深さ優先探索になるかとかそういう説明はおそらく怖い人がしているので
そちらに説明を譲ります
ここで問題になるのは
どう書き換えればスタックオーバーフローせずに
書けるかということです。
まず、stackに突っ込むデータを整理します。
要するに再帰するときに渡している引数が必要です
struct s{
int x,y;
};書きました。
初期化めんどくさいのでコンストラクタぐらいは書きましょう
struct s{
s(int X,int Y){
x=X;
y=Y;
}
int x,y;
};はい書きました。
solve関数の手術の準備は終わりました
再帰をしてはダメなので
solve関数内でsolve関数を呼び出さずに
結果を変えないように、solve関数を書き換えます
int solve(int x,int y){
int ans=1;
for(~~~~){
if(~~~~){
if(~~~~){
map[x][y]='#';
//再帰ans+=solve(x+vec[i][0],y+vec[i][1]);
}
}
}
return ans;
}とりあえず再帰してた部分をコメントアウトしました
当然結果は変わりますので、
再帰している部分をどうにか再現しないといけません。
再帰が何やっているかっていうと、
引数の状態での探索をもう一度繰り返している。
ということです。
なのでstackにでも探索したい状態を放り込んでおいてやって
取り出した状態を探索してやると良い感じになります
ではstackに状態がなくなるまで探索を続けるという風にコードを変形します
探索するたびに答えの値が一増えているのでans=1をans++とかにしてやります
int solve(int x,int y){
stack<s> st;
int ans=0;
while(st.empty()!=true){
ans++;
for(~~~~){
if(~~~~){
if(~~~~){
map[x][y]='#';
//再帰ans+=solve(x+vec[i][0],y+vec[i][1]);
}
}
}
}
return ans;
}このままでは当然whileループの中には入らないので（状態がstackに入ってない）
初期状態をstackに積みます
積んだのは取り出さないと行けないので
状態を取り出す処理も書きます
int solve(int x,int y){
stack<s> st;
//初期状態の追加
st.push(s(x,y));
int ans=0;
while(st.empty()!=true){
s tmp=st.top();st.pop();
x=tmp.x;y=tmp.y;
for~~~~~~~~~~~~~~~~~~
}
return ans;
}
あとは再帰をコメントアウトした部分を
探索待ちの状態をstackに積むというコードに書き換えます
int solve(int x,int y){
~~~~~~~~~~~~~~~~~~
while(st.empty()!=true){
ans++;
for(~~~~~~){
if((~~~~~~~~~~){
if(~~~~~~~~~~~~){
map[x][y]='#';
//再帰ans+=solve(x+vec[i][0],y+vec[i][1]);
st.push(s(x+vec[i][0],y+vec[i][1]));
}
}
}
}
return ans;
}これで通るはずです（ふぅ・・・
ね？簡単でしょう？（
P.S
stackをqueueに変更してやると
幅優先探索になります
取り出し処理のメソッドが違ったりとかしますが
変更点はほぼ一緒なので、
すぐに書けると思います
コード
int solve(int x,int y){
int ans=0;
map[x][y]='#';
queue<s> q;
q.push(s(x,y));
while(!q.empty()){
s n=q.front();q.pop();
x=n.x;
y=n.y;
ans++;
for(int i=0;i<4;i++){
if((x+vec[i][0]>=0)&&(y+vec[i][1]>=0)&&(x+vec[i][0]<h)&&(y+vec[i][1]<w)){
if(map[x+vec[i][0]][y+vec[i][1]]=='.'){
map[x+vec[i][0]][y+vec[i][1]]='#';
q.push(s(x+vec[i][0],y+vec[i][1]));
}
}
}
}
return ans;
}
