AtCoder 深さ優先探索がわかりません。

Question

前提・実現したいこと

AtCoderの深さ優先探索の問題についての質問です。以下のような迷路を入力し、ゴールまで到達可能な場合Yes、そうでない場合Noを出力する問題です。エラーは起こらないのですが、ゴールに到達可能な場合にもNoが表示されてしまいます。どこに問題があるのか教えていただきたいです。

10 10
...s......
#########.
#.......#.
#..####.#.
##....#.#.
#####.#.#.
..#.#.#.#.
#.#g#.#.#.
#.#.#.#.#.
#.....#...

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    
   int H,W,sx,sy,gx,gy,X,Y;
    
    cin>>H>>W;
    H--;W--;
    char raby[H][W];
    bool rireki[H][W];//それぞれのマスが通過済みの場合はtrueを代入する
    for(int i = 0; i<H+1; i++){
      for(int j = 0; j<W+1; j++){
        cin>>raby[i][j];
        rireki[i][j]=0;
        if(raby[i][j]=='s'){sx=i; sy=j;}//スタートの位置
        if(raby[i][j]=='g'){gx=i; gy=j;}//ゴールの位置

      }
    }
    const int vx[4]={1,0,-1,0};//上下左右の移動用の配列
    const int vy[4]={0,1,0,-1};
  
   rireki[sx][sy]=1;
    stack<pair<int,int>> rec;
    
    rec.push(make_pair(sx,sy));
    while(rec.empty()!=1){
      X=rec.top().first;
      Y=rec.top().second;
      rec.pop();
      
      for(int i = 0; i<4; i++){
        if(raby[X+vx[i]][Y+vy[i]]=='#'||rireki[X+vx[i]][Y+vy[i]]==1)continue;
//行先が壁だったり通過済みの場合はスルー
        if(X+vx[i]>=H||Y+vy[i]>=W||X+vx[i]<0||Y+vy[i]<0)continue;
//場外の場合もスルー
        if(raby[X+vx[i]][Y+vy[i]]=='.'||raby[X+vx[i]][Y+vy[i]]=='g'){
           rireki[X+vx[i]][Y+vy[i]]=1;
           rec.push(make_pair(X+vx[i],Y+vy[i]));
        }

      }
    }
  
    if(rireki[gx][gy]==1)cout<<"Yes"<<endl;
    if(rireki[gx][gy]==0)cout<<"No"<<endl;
    for(int i = 0; i<H+1; i++){
      for(int j = 0; j<W+1; j++){
        cout<<rireki[i][j];
      }  
    } 
}

試したこと

それぞれのマスを通過したときにrirekiに１を入れるつもりだったのですが、試しにrirekiの値を出力してみたところ、通過可能なマスに正しく１が代入できていませんでした。上のテストケースだと、一番上の行の右側の角のところまでしか１が代入されていません。他の人のコードを参考にしてみたりもしましたが、どこに問題があるのかがわかりませんでした。拙い内容で恐縮ですが、何卒解答よろしくお願いします。

Comments

[kuma_kuma_]

どちらかというと再帰関数の勉強だよね？
でも質問者様のコードを見ると再帰関数になっていない...
このまま完成させても再帰関数の勉強という意味では達成できていないことになる。
どうしたものか...

[72234]

ご指摘ありがとうございます。
kuma_kuma様のおっしゃる通り、AtCoderでもメインの解説は再帰関数を用いています。
ただ、解説を見ずに取り組んだ際に、思いついた解法がスタックを用いたものであったため、
まずはこちらの方法で正解しておこうと思った次第です。
再帰関数を用いた方法もやってみようと思います。

Answer 1

    H--;W--;

このコードは消し忘れですか? このデクリメントのせいで、縦H-1や横W-1を通るパスがすべて場外判定になってます。

    for(int i = 0; i<H+1; i++){
      for(int j = 0; j<W+1; j++){

このあたりのループも、このままでは範囲外のアクセスを起こします。もしかしたら上のデクリメントで減った分足してるのかもしれませんが、そもそもデクリメント必要ですか?

あと直接影響は出てないみたいですが、デクリメントしない場合でも下のコード

        if(raby[X+vx[i]][Y+vy[i]]=='#'||rireki[X+vx[i]][Y+vy[i]]==1)continue;
//行先が壁だったり通過済みの場合はスルー
        if(X+vx[i]>=H||Y+vy[i]>=W||X+vx[i]<0||Y+vy[i]<0)continue;
//場外の場合もスルー

この評価順序は範囲外アクセスを起こします。

Comments

[72234]

解答ありがとうございます。
デクリメントのところは、私が配列の要素数と添え字番号を混同したために起きたミスです。
ご指摘に沿って直したところ、解決することができました。
評価順序のところも自分では気づかなかったと思います。ご指摘ありがとうございます。