C++ 幅優先探索でタイムアウト

Question

前提・実現したいこと

幅優先探索を試す為、ATC001 A - 深さ優先探索の問題を幅優先探索の手法で出来るか試しています。
幅優先探索のループが抜けられず、タイムアウトしてしまいます。

発生している問題・エラーメッセージ

終了コード	9
実行時間	10607 ms
メモリ	101516 KB

該当のソースコード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
using vi = vector<int>;
using vvi = vector<vi>;
using pii = pair<int, int>;
  vi dx = {1, 0, -1, 0};
  vi dy = {0, 1, 0, -1};

int main(){
  int H, W; cin >> H >> W;
  int sx, sy, gx, gy;
  vector<vector<char>> maze(H, vector<char>(W));
  rep(i,H){
    rep(j,W){
      cin >> maze[i][j];
      if(maze[i][j] == 's') {sx=i; sy = j;}
      if(maze[i][j] == 'g') {gx=i; gy = j;}
    }
  }

  vvi status(H,vi(W,-1));
  queue<pii> que; 
  que.push(pii(sx,sy));
  while(!que.empty()){
    int x, y;
    x = que.front().first;
    y = que.front().second;
    status[x][y] = 1;

    rep(i,4){
      int ny = y+dy[i];
      int nx = x+dx[i];
      if(nx<0 || nx>=H || ny<0 || ny>=W) continue;
      if(maze[nx][ny] == '#') continue;
      if(status[ny][nx] < 0){
        status[nx][ny] = 0;
        que.push(pii(nx,ny));
      }
    }
    que.pop();
  }
  if(status[gy][gx] > 0 ) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;         
}

試したこと

statusの状況を確認すると初期 -1, queue に入れた時点で 0, 探索時に1とするようにし、ここが動いていないようでしたが原因がわかりません。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Answer 1

  if(status[ny][nx] < 0){
    status[nx][ny] = 0;

if(status[gy][gx] > 0 ) cout << "Yes" << endl;

[y][x]なのか[x][y]なのか考え直すといいです。

Comments

[Syul]

ありがとうございます。簡単なところを見落としていました。

Answer 2

????
通常、幅優先は深さ優先に比べて速度は速い（代わりにメモリ消費が激しい）はずです。メモリを使い切ってエラー停止する可能性はありますが、速度が遅くなるのは変です。

遅くなったわけではなく、バグの可能性があると考えられます。