Submission #1687281

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

//http://atc001.contest.atcoder.jp/tasks/dfs_a

#define RESIDUE(u,v) (capacity[u][v] - flow[u][v])
#define RCOST(u,v) (cost[u][v] + h[u] - h[v])
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)

#define MAX 500

vector<string> v;
bool reach[MAX][MAX];
int h,w;

void dfs(int y,int x){
  //cout<<y<<" "<<x<<endl;
  if(reach[y][x])
    return;
  reach[y][x]=true;
  if(y>0 && v[y-1][x]!='#')
    dfs(y-1,x);
  if(y<h-1 && v[y+1][x]!='#')
    dfs(y+1,x);
  if(x>0 && v[y][x-1]!='#')
    dfs(y,x-1);
  if(x<w-1 && v[y][x+1]!='#')
    dfs(y,x+1);
}

int main(){
  string s;
  int sh,sw,gh,gw;
  cin>>h>>w;
  REP(i,h){
    cin >> s;
    v.push_back(s);
  }
  REP(i,h){
    REP(j,w){
      reach[i][j]=false;
      if(v[i][j]=='s'){
	sh=i;
	sw=j;
      }
      if(v[i][j]=='g'){
	gh=i;
	gw=j;
      }
    }
  }
  dfs(sh,sw);
  cout<< (reach[gh][gw]?"Yes":"No") <<endl;
  return 0;
}

Submission Info

Judge Result