Submission #421361

---

Source Code Expand

#include <iostream>
#include <bitset>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;

int S,G;
const int mawari[4]={-512,-1,+1,+512};
bitset<(512*512)> ok(0);
bitset<(512*512)> notToGoal(0);
/*
bool rec(int ax){
    notToGoal.set(ax);
    for(int i=0;i<4;++i){
        int x=ax+mawari[i];
        if( x==G ){return true;}
        if( ok.test(x) ){
            if( !notToGoal.test(x) && rec(x) ){
                return true;
            }
        }
    }
    return false;
}*/

int main(){
    int H,W;
	cin>>H>>W;
    for(int h=1;h<=H;++h){
        string str;
        cin>>str;
        for(int w=1;w<=W;++w){
            int x=h*512+w;
            switch(str[w-1]){
                case 's':S=x;break;
                case 'g':G=x;break;
                case '.':ok.set(x);break;
                case '#':break;
            }
        }
    }/*
    if( rec(S) ){
        cout<<"Yes"<<endl;
    }else{
        cout<<"No"<<endl;
    }*/
    stack<int> st;
    int ax=S;
START:
    notToGoal.set(ax);
    for(int i=0;i<4;++i){
        int x=ax+mawari[i];
        if( x==G ){cout<<"Yes"<<endl;return 0;}
        if( ok.test(x) ){
            if( !notToGoal.test(x) ){
                st.push(ax);
                ax=x;
                goto START;
            }
        }
    }
    if(st.size()){
        ax=st.top();
        st.pop();
        goto START;
    }
    cout<<"No"<<endl;
    return 0;
}

Submission Info

Judge Result