蟻本の”迷路の最短路”の問題について自分の回答の誤りがわからない

Question

前提・実現したいこと

大きさがN×Mの迷路があります。迷路は通路('.')と壁'#'からできており、１ターンに隣接する上下左右４マスの通路へ移動することができます。スタート('S')からゴール('G')まで移動するのに必要な最小ターン数を求めなさい。
M, N <= 100

という問題があり、以下のように解きましたが、答えが0になってしまいます。この原因を教えていただけますか。よろしくお願いします。

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int INF = 1e8;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int N, M; 
vector<string> maze;
int d[110][110];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int sx, sy, gx, gy;
typedef pair<int, int> P;


int bfs(){
    queue<P> que;

    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j) d[i][j] = INF;
    }
    que.push(P(sx, sy));
    d[sy][sx] = 0;
    while(que.size()){
        P p = que.front(); que.pop();
        int px = p.first, py = p.second;
        if(px == gx && py == gy) break;
        for(int i = 0; i < 4; ++i){
            int nx = px + dx[i], ny = py + dy[i];
            if(nx >= 0 && nx < M && ny >= 0 && ny < N && maze[ny][nx] != '#' && d[ny][nx] == INF){
                que.push(P(nx, ny));
                d[ny][nx] = d[py][px] + 1;
            }
        }
    }

    return d[gy][gx];
}


void solve(){
    cout << bfs() << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M; cin >> M >> N;
    maze.resize(N); 

    for(int i = 0; i < N; ++i) cin >> maze[i];
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < M; ++j){
            if(maze[i][j] == 'S'){
                sx = j; sy = i;
            }
            if(maze[i][j] == 'G'){
                gx = j; gy = i;
            }
        }
    }
    solve();

}

Answer 1

int N, M; cin >> M >> N; // ローカル変数のN,Mに代入している

Comments

[rdld036]

指摘していただきありがとうございます。