Submission #4482959

---

Source Code Expand

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <queue>

using namespace std;

int main(){
  int H,W; cin>>H>>W;
  vector<vector<char> > map(H,vector<char>(W));
  vector<vector<bool> > check(H,vector<bool>(W,false));

  int sh,sw,gh,gw;
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>map[i][j];
      if(map[i][j]=='s'){
        sh=i; sw=j;
      }
      if(map[i][j]=='g'){
        gh=i; gw=j;
      }
    }
  }

  queue<int> h,w;
  h.push(sh); w.push(sw);
  check[sh][sw]=true;
  while(!h.empty()){
    int th=h.front(),tw=w.front();
    h.pop(); w.pop();
    if(th==gh&&tw==gw){
      cout<<"Yes"<<endl;
      return 0;
    }
    if(th<H-1){
      if(map[th+1][tw]!='#'&&!check[th+1][tw]){
        h.push(th+1); w.push(tw);
        check[th+1][tw]=true;
      }
    }
    if(tw<W-1){
      if(map[th][tw+1]!='#'&&!check[th][tw+1]){
        h.push(th); w.push(tw+1);
        check[th][tw+1]=true;
      }
    }
    if(th>0){
      if(map[th-1][tw]!='#'&&!check[th-1][tw]){
        h.push(th-1); w.push(tw);
        check[th-1][tw]=true;
      }
    }
    if(tw>0){
      if(map[th][tw-1]!='#'&&!check[th][tw-1]){
        h.push(th); w.push(tw-1);
        check[th][tw-1]=true;
      }
    }
  }

  cout<<"No"<<endl;

  return 0;
}

Submission Info

Judge Result