Submission #420559

---

Source Code Expand

#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include <cmath>
#include <tuple>
#include <stack>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
 
 
using namespace std;
class SearchQueue{
 public:
  int x,y,d;
  SearchQueue(int x_,int y_, int d_):x(x_),y(y_),d(d_){}
};
int main(int, char** ){
    cin.tie(nullptr); ios::sync_with_stdio(false);
 
    int h,w;
    cin >> h >> w;
    string str;
    vector<vector<bool>> is_wall(h,vector<bool>(w,false));
    vector<vector<bool>> is_searched(h,vector<bool>(w,false));
    tuple<int,int> s,g;
    for(int i = 0; i < h; ++i){
        cin >> str;
        for(int j = 0; j < w; ++j){
            char c = str[j];
            if(c == 's'){
                s=make_tuple(i,j);
            }else if(c == 'g'){
                g=make_tuple(i,j);
            }else if(c == '#'){
                is_wall[i][j] = true;
            }    
        }
    }
    queue<SearchQueue> sqs;
    sqs.push(SearchQueue(get<0>(s),get<1>(s),0));
    int dxy[] = {0,-1,0,1,0};
    while(!sqs.empty()){
        SearchQueue sq = sqs.front(); sqs.pop();
        if(get<0>(g)==sq.x&&get<1>(g)==sq.y){
            cout << "Yes" << endl;
            return 0;
        }
        for(int i = 0; i < 4; ++i){
            int nx = sq.x+dxy[i], ny = sq.y+dxy[i+1];
            if(0<=nx&&nx<h&&0<=ny&&ny<w&&!(is_wall[nx][ny])&&!(is_searched[nx][ny])){
                sqs.push(SearchQueue(nx,ny,sq.d+1));
            }
        }
    }
 
    cout << "No" << endl;
 
    return 0;
}

Submission Info

Judge Result