問題

スタート地点からゴール地点まで到達可能かを判断するよくあるグリッドBFSなのですが、今回は2回まで壁を壊していいとのこと。

考察

今回は幅優先探索はある程度知っている体で説明していきます。
そもそも幅優先探索ってなに？っていう方はこちらのけんちょんさんの記事に分かりやすく書いてあります。

qiita.com また、グリッドBFSの実装についてはこの問題を参考にしてみてください。

さて、今回は普通のBFSとは違い通路の移動にはコストはかからず、壁を壊すときにのみ1のコストが発生します。
なので 0-1-BFS というものを使います。（私もこの問題で知りました）

方針

探索の仕方は普通のBFSと同じなのですが、queueへの追加の仕方が異なります。
今回は通路の移動のコストがかからないので通路を優先して探索する必要があります。
そのため、今回はqueueではなくdequeを使います。
通路の座標は優先して探索する必要があるためdequeの先頭に追加し、壁の座標は通常通りdequeの末尾に追加します。
コスト0の移動から優先して探索するのであとから最小値が再び更新されることはなくまた同じマスからの探索をせずに済みます。
このことを除けばあとは普通のBFSになります。

実装

上記のことを実装していきます

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int h, w;
    int sy, sx;
    int gy, gx;
    int dy[] = {-1, 0, 0, 1};
    int dx[] = {0, -1, 1, 0};

    cin >> h >> w;

    //各座標への移動コストを大きい値で初期化
    vector<vector<int>> cost(h, vector<int>(w, 9999));
    //各座標が壁か通路か
    vector<vector<char>> area(h, vector<char>(w));

    //迷路の入力
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> area[i][j];
            //スタート座標, ゴール座標をメモする
            if(area[i][j] == 's') sy = i, sx = j;
            else if(area[i][j] == 'g') gy = i, gx = j;
        }
    }

    //今回はdequeなことに注意
    deque<pair<int, int>> q;

    //スタート地点の座標をpushしcostを0にする
    q.push_back({sy, sx});
    cost[sy][sx] = 0;

    while(!q.empty()){
        //dequeの先頭のこれから探索する座標
        int y = q.front().first;
        int x = q.front().second;
        q.pop_front();
        for(int i = 0; i < 4; i++){
            //次に探索する座標
            int ny = y + dy[i];
            int nx = x + dx[i];
            //座標が不適当なら探索しない
            if(ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            //探索先が壁で, 移動costを更新するとき
            if(area[ny][nx] == '#' && cost[y][x] + 1 < cost[ny][nx]){
                cost[ny][nx] = cost[y][x] + 1;
                q.push_back({ny, nx});
            }
            //探索先が壁ではなく, 移動costを更新するとき
            else if(area[ny][nx] != '#' && cost[y][x] < cost[ny][nx]){
                cost[ny][nx] = cost[y][x];
                q.push_front({ny, nx});
            }
        }
    }

    //ゴール地点の移動costが2以下ならYES
    if(cost[gy][gx] <= 2) cout << "YES\n";
    else cout << "NO\n";

    return 0;
}