Submission #3006037

---

Source Code Expand

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

struct edge{ll to, cost;};
typedef pair<ll,ll> P;
struct graph{
  ll V;
  vector<vector<edge> > G;
  vector<ll> d;

  graph(ll n){
    init(n);
  }

  void init(ll n){
    V = n;
    G.resize(V);
    d.resize(V);
    REP(i,V){
      d[i] = INF;
    }
  }

  void add_edge(ll s, ll t, ll cost){
    edge e;
    e.to = t, e.cost = cost;
    G[s].push_back(e);
  }

  void dijkstra(ll s){
    REP(i,V){
      d[i] = INF;
    }
    d[s] = 0;
    priority_queue<P,vector<P>, greater<P> > que;

    que.push(P(0,s));
    while(!que.empty()){
      P p = que.top(); que.pop();
      ll v = p.second;
      if(d[v]<p.first) continue;
      for(auto e : G[v]){
        if(d[e.to]>d[v]+e.cost){
          d[e.to] = d[v]+e.cost;
          que.push(P(d[e.to],e.to));
        }
      }
    }
  }
};

int main(){
  ll h,w;
  cin >> h >> w;
  graph mp(h*w);
  char c[h][w];
  ll s,g;
  REP(i,h)REP(j,w){
    cin >> c[i][j];
    if(c[i][j]=='s') s = i*w+j;
    if(c[i][j]=='g') g = i*w+j;
  }
  REP(i,h-1)REP(j,w){
    mp.add_edge((i+1)*w+j,i*w+j,(c[i][j]=='#')?1:0);
    mp.add_edge(i*w+j,(i+1)*w+j,(c[i+1][j]=='#')?1:0);
  }
  REP(i,h)REP(j,w-1){
    mp.add_edge(i*w+j,i*w+j+1,(c[i][j+1]=='#')?1:0);
    mp.add_edge(i*w+j+1,i*w+j,(c[i][j]=='#')?1:0);
  }
  mp.dijkstra(s);
  if(mp.d[g]>2){
    cout << "NO" << endl;
  }else{
    cout << "YES" << endl;
  }
  return 0;
}

Submission Info

Judge Result