Submission #750483

---

Source Code Expand

#include <iostream>
#include <vector>
#include <utility>
#include <cstdio>
#include <stack>
#include <string>
using namespace std;

int main(void){
  int h, w;
  pair<int, int> start, goal;
  int ud[4] = {-1, 0, 1, 0};
  int lr[4] = {0, 1, 0, -1};
  string str;

  cin >> h >> w;
  vector<vector<char> > map(h, vector<char>(w));
  for(int i = 0; i < h; i++){
    cin >> str;
    for(int j = 0; j < w; j++){
      map[i][j] = str[j];
      if(map[i][j] == 's'){ start = make_pair(i, j); }
      if(map[i][j] == 'g'){ goal = make_pair(i, j); }
    }
  }

  stack<pair<int, int> > s;
  s.push(start);
  while(!s.empty()){
    pair<int, int> nowpoint = s.top();
    s.pop();
    //printf("[%d][%d]\n", nowpoint.first, nowpoint.second);
    if(nowpoint == goal){
      cout << "Yes" << endl;
      return 0;
    }

    // 周囲四方向を見る
    map[nowpoint.first][nowpoint.second] = '#';
    for(int i = 0; i < 4; i++){
      int next_x = nowpoint.first + ud[i];
      int next_y = nowpoint.second + lr[i];
      if(0 <= next_x && next_x < h && 0 <= next_y && next_y < h && map[next_x][next_y] != '#'){
        s.push(make_pair(next_x, next_y));
      }
    }
  }

  cout << "No" << endl;
  return 0;
}

Submission Info

Judge Result