Submission #3996193

---

Source Code Expand

/**
 * AtCoder Typecal Contest 001
 * A - 深さ優先探索
 *
 * DFSパターン
 */
#include <iostream>
#include <queue>
using namespace std;

using P = pair<int, int>;

#define MAX_H 500
#define MAX_W 500

int H, W;
char maze[MAX_H][MAX_W + 1];
bool reached[MAX_H][MAX_W];
int sh{-1}, sw{-1}, gh{-1}, gw{-1};

int dh[4]{1,  0, -1,  0};
int dw[4]{0,  1,  0, -1};

bool bfs() {
  queue<P> que;
  que.push(P(sh, sw));
  reached[sh][sw] = true;

  while (que.size()) {
    P p = que.front(); que.pop();
    if (p.first == gh && p.second == gw) return true;
    for (int i{}; i < 4; ++i) {
      int nh = p.first + dh[i];
      int nw = p.second + dw[i];
      if (nh < 0 || nh >= H ||
          nw < 0 || nw >= W ||
          maze[nh][nw] == '#' ||
          reached[nh][nw])
        continue;
      que.push(P(nh, nw));
      reached[nh][nw] = true;
    }
  }

  return false;
}

int main() {
  scanf("%d%d", &H, &W);
  for (int i{}; i < H; ++i) {
    scanf("%s", maze[i]);
    if (sh < 0 || gh < 0) {
      for (int j{}; j < W; ++j) {
        if (maze[i][j] == 's') {
          sh = i; sw = j;
        } else if (maze[i][j] == 'g') {
          gh = i; gw = j;
        }
      }
    }
  }

  printf("%s\n", bfs() ? "Yes" : "No");
  return 0;
}

Submission Info

Judge Result