Submission #423251

---

Source Code Expand

#include <iostream>
#include <vector>
#include <numeric>
#include <map>
#include <stack>

using namespace std;

bool walkable(int x, int y, char r[][500]) {
  if (x < 0 || x >= 500 || y < 0 || y >= 500) {
    return false;
  } else if (r[y][x] == '#' || r[y][x] == 'w') {
    return false;
  } else if (r[y][x] == '.' || r[y][x] == 'g') {
    return true;
  }
}

int main(void) {
  int h, w;
  int sy, sx, gy, gx;
  char rab[500][500] = {0};

  cin >> h >> w;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> rab[i][j];
      char c;
      if ((c = rab[i][j]) == 's') {
        sx = j;
        sy = i;
      } else if (c == 'g') {
        gx = j;
        gy = i;
      }
    }
  }
  /*
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cout << rab[i][j];
    }
    cout << endl;
  }
  */
  stack<pair<int,int> > sp;
  sp.push(pair<int, int>(sx, sy));
  while (!sp.empty()) {
    int x, y;
    pair<int, int> pii = sp.top();
    x = pii.first;
    y = pii.second;
    sp.pop();
    // cout << x << y << endl;
    if (rab[y][x] == 'w') {
      continue;
    } else if (rab[y][x] ==  'g') {
      cout << "Yes" << endl;
      return 0;
    }
    /*
    for (int i = 0; i < h; i++) {
      for (int j = 0; j < w; j++) {
        cout << rab[i][j];
      }
      cout << endl;
    }
    cout << endl;
    */
    rab[y][x] = 'w';
    if (walkable(x - 1 , y, rab)) {
      sp.push(pair<int, int>(x - 1, y));
    }
    if (walkable(x + 1 , y, rab)) {
      sp.push(pair<int, int>(x + 1, y));
    }
    if (walkable(x, y - 1, rab)) {
      sp.push(pair<int, int>(x, y - 1));
    }
if (walkable(x, y + 1, rab)) {
      sp.push(pair<int, int>(x, y + 1));
    }
  }
  cout << "No" << endl;
  return 0;
}

Submission Info

Judge Result