Submission #2531782

---

Source Code Expand

#include <bits/stdc++.h>

#define foreach(i, v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)

using namespace std;
typedef long long ll;

int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int dist[600][600];
int h,w;
int sy,sx, gy,gx;
std::vector<string> mp(600);

int main(int argc, char *argv[]) {
  ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

  int h,w;cin>>h>>w;

  for(int y=0;y<h;y++){
    cin>>mp[y];
    if(mp[y].find("s")!=string::npos){
      sx = mp[y].find("s");
      sy = y;
    }
    if(mp[y].find("g")!=string::npos){
      gx = mp[y].find("g");
      gy = y;
    }
  }
  // cout<<sx<<':'<<sy<<endl;

  queue<int> q;
  q.push(sy);
  q.push(sx);
  dist[sy][sx]=1;
  while(q.size()){
    int y = q.front();q.pop();
    int x = q.front();q.pop();
    for(int i=0;i<4;i++){
      int ny= y + dy[i];
      int nx= x + dx[i];
      if(!(0<=ny&&ny<h&&0<=nx&&nx<w))continue;
      int wei = (mp[ny][nx]=='#') ? 1000001 : 1;
      if(dist[y][x]+wei>3000000)continue;
      if(dist[ny][nx] && dist[ny][nx]<=dist[y][x]+wei)continue;
      q.push(ny);
      q.push(nx);
      dist[ny][nx] = dist[y][x]+wei;
    }
  }
  // for(int i=0;i<h;i++){
  //   for(int j=0;j<w;j++)
  //     cout<<dist[i][j];
  //   cout<<endl;
  // }

  if(dist[gy][gx]){
    cout<<"YES"<<endl;
  }else{
    cout<<"NO"<<endl;
  }

  return 0;
}

Submission Info

Judge Result