01BFSクラスで解く、器物破壊高橋君

ライブラリ 
struct ZeroOneBFS{
  ll H,W;
  VS S;
  VV d; // distance

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

  bool in_range(ll i, ll j){
    if(0<=i && i<H && 0<=j && j<W){
      return true;
    }else{
      return false;
    }
  }

  ZeroOneBFS(VS _S){
    S = _S;
    H = S.size();
    W = S[0].size();
    d.resize(H, VI(W,-1));
  }

  // その文字を1つ見つけて場所を返す(y,x)
  PII search(char c){
    rep(i,H){
      rep(j,W){
        if(S[i][j]==c)return PII(i,j);
      }
    }
    debug("not found");return PII(-1,-1);
  }

  // 文字（地図）更新
  void update(ll y, ll x, char c){
    S[y][x] = c;
  }
  void update(PII pos, char c){
    update(pos.first, pos.second, c);
  }

  void debug_print(){
    rep(i,H){
      debug(d[i]);
    }
  }

  // start位置から01bfs
  void calc(PII start){
    deque<PII> que;
    que.push_back(start);
    d[start.first][start.second]=0;

    while(!que.empty()){
      PII a = que.front(); que.pop_front();
      ll y=a.first;
      ll x=a.second;
      // 上下左右を見る
      rep(i,4){
        ll ny = y + dy[i];
        ll nx = x + dx[i];
        if(!in_range(ny,nx))continue;
        if(d[ny][nx]!=-1)continue;
        if(S[ny][nx]=='.'){
          d[ny][nx] = d[y][x];
          que.push_front({ny,nx}); // 前に入れる
        }else{
          d[ny][nx] = d[y][x]+1;
          que.push_back({ny,nx}); // 後に入れる
        }
      }
    }
  }

  ll distance(PII pos){
    return d[pos.first][pos.second];
  }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll H,W;cin>>H>>W;
    VS S(H);
    rep(i,H)cin>>S[i];

    auto bfs = ZeroOneBFS(S);
    auto start = bfs.search('s');
    auto goal = bfs.search('g');
    bfs.update(start,'.');
    bfs.update(goal,'.');
    bfs.calc(start);
    if(bfs.distance(goal)<=2)yes();
    no();
    
    return 0;
}