競プロ典型90問 - 43 Maze Challenge with Lack of Sleep（★4）

問題https://atcoder.jp/contests/typical90/tasks/typical90_aq
解説 https://twitter.com/e869120/status/1394787605099601923/photo/1

【問題】
二次元迷路のスタートからゴールへの経路のうち、最も曲がる回数が少ない経路の回数を求めよ
【典型ポイント】
頂点拡張
0-1 BFS
【注意点】
頂点拡張するので、同じ頂点を複数回更新することがある。
→遷移先のコストと現在の最小コストを比較し、更新可能ならキューに詰める。
この処理を適切に行わないと無限ループに陥ったり、更新すべき点が更新されなかったりするので注意
【方針】
通常の最短経路問題とは違い、曲がる回数の最小値を求める。
曲がる回数は移動ごとに+0 または +1 されるので、dequeを用いた0-1BFSで実装できる。

次のマスに移動するときに、曲がったかどうかの判定には「いまどの方向を向いているか(どの方向から来たか)」の情報が必要。
各マスごとに、移動する向きごとに4つに拡張することで対処する。拡張BFSとか、拡張ダイクストラとか言うらしい。

【感想】
同一頂点が複数分割される点は問題なかったが、遷移の条件を間違えまくって時間を溶かしてしまった

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007;
constexpr long long INF = 1000000000 + 100;
constexpr long long LINF = 1000000000000000000 + 100;
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
#define rrep(i, n) for(int i=(n); i>=0; i--)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

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

using tup = tuple<int, int, int>;

int cost[1010][1010][4];
int main(){
    int H, W, sy, sx, gy, gx;
    cin >> H >> W >> sy >> sx >> gy >> gx; sy--, sx--, gy--, gx--;
    vector<string> g(H); rep(i, H)cin >> g[i];

    rep(i, H)rep(j, W)rep(k, 4)cost[i][j][k] = INF;

    //0-1 bfs
    deque<tup> que;
    rep(k, 4){
        que.push_back({sy, sx, k});
        cost[sy][sx][k] = 0;
    }
    while(!que.empty()){
        auto t = que.front(); que.pop_front();
        int y = get<0>(t), x = get<1>(t), d = get<2>(t);
        rep(k, 4){
            int ny = y+dy[k], nx = x+dx[k];
            if(ny<0 or nx<0 or ny>=H or nx>=W or g[ny][nx]=='#')continue;
            int nxc = cost[y][x][d] + (d == k ? 0 : 1);
            if(cost[ny][nx][k] > nxc){ //更新発生
                cost[ny][nx][k] = nxc;
                if(d==k)que.push_front({ny, nx, k});
                else que.push_back({ny, nx, k});
            }
        }
    }
    cout << *min_element(cost[gy][gx], cost[gy][gx]+4) << ln;
}