C++のメッセージ無しでの強制終了で困っています

Question

はじめまして，今回が本サイトでの初めての質問になります．
最近競技プログラミングを始めるためにC++を勉強しているのですが，言語仕様が分からない故のバグに日々悩まされています．

AtcoderTypicalContest001 A問題「深さ優先探索」のためのソースコード（下記）についてなのですが，
'#'を塀，'.'を道としてスタート地点（'s'）からゴール地点（'g'）までたどり着くことが出来るかどうかを判定する問題です．
以下のソースコード及びテストパターンにおいて，何らかのメッセージも無しに強制終了してしまいます．
最終的に"Yes"もしくは"No"を返すはずだと思うのですが出力が出てくれません．

強制終了の原因もしくは解決策があれば教えて頂きたいです．

OSはwindows，開発環境はvisual studio codeを使用しています．

###ソースコード

#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define repr(i, n) for(int i = (int)(n); i >= 0; i--)
#define repm(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define repmr(i, m, n) for(int i = (int)(n); i >= (int)(m); i--)
#define all(x) (x).begin(),(x).end()
#define inf 2e9

using namespace std;
typedef long long int lli;
typedef long long ll;

int main() {
    int h,w;
    cin >> h >> w;
    vector<vector<char>> c(h, vector<char>(w));
    vector<int> start(2);
    rep(i,h) rep(j,w){
        cin >> c[i][j];
        if(c[i][j] == 's'){
            start[0] = i;
            start[1] = j;
        }
    }

    vector<vector<bool>> rout(h, vector<bool>(w, false));
    stack<vector<int>> st;
    st.push(start);
    bool goal = false;
    while(st.size() != 0){
        vector<int> now = st.top();
        if(c[now[0]][now[1]] == 'g'){
            goal = true;
            break;   
        }
        st.pop();
        rout[now[0]][now[1]] = true;
        if(now[0]-1 >= 0 && c[now[0]-1][now[1]] != '#' && !rout[now[0]-1][now[1]]){
            st.push({now[0]-1, now[1]});
            cout << st.top()[0] << " " << st.top()[1] << endl;
        }
        if(now[0]+1 < h && c[now[0]+1][now[1]] != '#' && !rout[now[0]+1][now[1]]){
            st.push({now[0]+1, now[1]});
            cout << st.top()[0] << " " << st.top()[1] << endl;
        }
        if(now[1]-1 >= 0 && c[now[0]][now[1]-1] != '#' && !rout[now[0]][now[1]-1]){
            st.push({now[0], now[1]-1});
            cout << st.top()[0] << " " << st.top()[1] << endl;
        }
        if(now[1]+1 < w && c[now[0]][now[1]+1] != '#' && !rout[now[0]-1][now[1]+1]){
            st.push({now[0], now[1]+1});
            cout << st.top()[0] << " " << st.top()[1] << endl;
        }
    }

    cout << ((goal) ? "Yes":"No") << endl;

}

入力内容

4 4
...s
....
....
.g..

出力内容

stackにpushする内容を毎回出力しています．

1 3
0 2
1 2
0 1

ここで出力が途切れ，何のメッセージもなく強制終了します．

Comments

[showkit]

オペレーティングシステムは何を使用していますか？ Unix/Linux 系であれば、デバッグモードで make して core を出力させれば、デバッガでどこで こけたかを確認できますが・・・。

[tacsheaven]

実際に Linux 上で gcc(g++) でコンパイルして動かすと Segmentation Fault 起こしますね。

[chan_yu1224]

OSはWindowsなので確認できないです...
開発環境はVSCodeを使用しています．
VisualStudioでウォッチを使いたいのですが今容量不足で入れることが出来ないので...

Answer 1

このプログラムの探索アルゴリズムを見てみましょう。

stack に push されている内容は、現在の座標位置を表しています（y, x の順のようですが）
そして探索の手順として、

1. 現在位置の上が座標外ではなく、堀でもなく、探索済み（rout[][] が true）でもないなら、現在位置を一つ上へずらす
2. 現在位置の下が座標外ではなく... なら、現在位置を一つ下へずらす
3. 現在位置の左が座標外ではなく... なら、現在位置を一つ左へずらす
4. 現在位置の右が座標外ではなく... なら、現在位置を一つ右へずらす

これを踏まえた上で読むと、一カ所おかしなところがあります。

    while(st.size() != 0){
        vector<int> now = st.top();
        if(c[now[0]][now[1]] == 'g'){
            goal = true;
            break;   
        }
        st.pop();
        rout[now[0]][now[1]] = true;
        if(now[0]-1 >= 0 && c[now[0]-1][now[1]] != '#' && !rout[now[0]-1][now[1]]){
            st.push({now[0]-1, now[1]});
            cout << st.top()[0] << " " << st.top()[1] << endl;
        }
        if(now[0]+1 < h && c[now[0]+1][now[1]] != '#' && !rout[now[0]+1][now[1]]){
            st.push({now[0]+1, now[1]});
            cout << st.top()[0] << " " << st.top()[1] << endl;
        }
        if(now[1]-1 >= 0 && c[now[0]][now[1]-1] != '#' && !rout[now[0]][now[1]-1]){
            st.push({now[0], now[1]-1});
            cout << st.top()[0] << " " << st.top()[1] << endl;
        }
        if(now[1]+1 < w && c[now[0]][now[1]+1] != '#' && !rout[now[0]-1][now[1]+1]){
            st.push({now[0], now[1]+1});
            cout << st.top()[0] << " " << st.top()[1] << endl;
        }
    }

問題はこの if 群の4番目にあります。
探索済みかどうかは、動く「先」を確認するものですから、rout[now[0]-1][now[1]+1] はおかしいですね。
rout[now[0]][now[1]+1] でないといけないはずです。

結果どうなるかというと、四歩目の時点で (0, 1) にいますから、五歩目として rout[-1][2] を見ようとして、範囲外アクセスが起きて Segmentation fault になりますね。

Comments

[chan_yu1224]

回答ありがとうございます．
完全に確認を怠っておりました....（お恥ずかしい）

言語仕様の問題以前の問題でした．
次からは気を付けてコーディングします．

ありがとうございました！

[tacsheaven]

ちなみに三歩目のとき（（1,3)->(0,2) の次）のときは、nowが（0,3）であるため、now[1]+1 < w の条件が満たされず rout へのアクセスが行われなかったために Segmentation Fault にならないのです。

Answer 2

落ちた所とウォッチした値を貼っておきます。