Submission #3433353

---

Source Code Expand

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int field[509][509];
bool visit[509][509];
int H, W;
pii S, G;

bool bfs(){
    
    int dh[] = { -1, 0, 1, 0};
    int dw[] = { 0, 1, 0, -1};
    
    mem(visit,false);
    visit[S.first][S.second]=true;
    vector<pii> now;
    now.push_back({S.first,S.second});
    
    while(now.size()){
        vector<pii> nxt;
        for(auto p:now){
            if(p.first==G.first && p.second==G.second)return true;
            int ph = p.first;
            int pw = p.second;
            rep(i,4){
                int nh = ph + dh[i];
                int nw = pw + dw[i];
                if(nh>=1 && nw>=1 && nh<=H && nw<=W){
                    if(visit[nh][nw]) continue;
                    visit[nh][nw]=true;
                    if(field[nh][nw]==2) field[nh][nw]=1;
                    if(field[nh][nw]==0){
                        nxt.push_back(make_pair(nh,nw));
                        
                    }
                }
            }
        }
        swap(now,nxt);
    }
    return false;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin>>H>>W;
    
    rep1(i,H)rep1(j,W){
        char c; cin>>c;
        if(c=='#') field[i][j]=2;
        else if(c=='.') field[i][j]=0;
        else if(c=='s'){ S.first=i; S.second=j;
        }else{ G.first=i; G.second=j;}
    }
    
    field[S.first][S.second] = 0;
    field[G.first][G.second] = 0;
    
    rep(i,3){
        if(bfs()){
            cout1("YES");
            return 0;
        }else{
            rep1(k,H)rep1(j,W){
                if(field[k][j]==1) field[k][j]=0;
            }
        }
    }
    cout1("NO");
}

Submission Info

Judge Result