Atcoder競プロ典型 90 問 043 - Maze Challenge with Lack of Sleep（★4）を ダイクストラ法で解く

17499 ワード
典型90問 C++ 競技プログラミング ダイクストラ法 C++ テキストリンク

この問題は、BFSで考えるのが適当です。それをダイクストラ法で解きます

公式解説
https://twitter.com/e869120/status/1394787605099601923

題意

  • 迷路があり、任意のスタートとゴール(s,tとします)があります。sからtに移動したいです。
  • 最初どの方向を向いていても良く、ゴール時にどの方向でも良いです。
  • 向いている向きに進むのコスト0です。向きを変えるコストを1とします。
  • sからtに向かう最小コストを求めてください。
  • 制約: 迷路の大きさ$h \times w$ で、それぞれ1000以下

こう考えた

ダイクストラ法で以下のように考えました。

左の迷路があったとき、

  • 右のように４つの{上, 右, 下, 左}にしか移動できない迷路を考えます。それぞれ移動できる先が壁でなければあるマスから移動先に対してcost 0の辺を張ります。
  • 4つの迷路は各迷路の同じマス同士でcost 1の辺を張ります。例えば、上に移動できる迷路の$(0,0)$は、{右, 下, 左}の迷路にcost 1で移動できます。これは両方向に辺を張ります。
  • スタートとゴールの向きを(無視することを)考慮するため、特別な辺s, tを作ります。
    • sはcost 0でスタートの各向きのマスに対して計4本辺を張ります
    • tは同様に、各向きのマスから辺を張ります
  • s->tにダイクストラ法で最短経路を求めます

実装について

$1000 \times 1000$は一見小さいように見えますが、$1e6$と意外に多いです。最大の必要な辺と頂点の数を考察してみましょう。

  • 頂点は各マスであるため$1e6 + 2$必要になります
  • 辺は約$1.6 \times 1e7$必要になります。
    • s,tからの各辺は8本です(ほぼ無視できます)
    • 各マスの向き間の辺は$1.2 \times 1e7 $本です。各マスは有向辺で各向きと張るためです。
    • 各向きの迷路の辺は最大で約$1e6$のため、合計で$4e6$本必要になります

Pythonでは制限時間内に解くのは難しいです。

実装

特に注意する点はない、のですが、辺や頂点が多いので、適切な型でリソースを確保しましょう。(例えば、ダイクストラの各ノードのコストはintの範囲に収まりますが、shortの範囲には収まりません。long longでは過剰です)

void solve(){
    int h, w; cin >> h >> w;
    int r1,c1,r2,c2; cin >> r1>>c1>>r2>>c2;
    --r1; --r2; --c1; --c2;
    char maze[h*w];
    memset(maze, 0, sizeof(maze));
    REP(hh, h) REP(ww, w) cin >> maze[hh*w + ww];
    int masu = h*w; // この迷路のマス数
    dijkstra<int> dj(4*masu + 2);
    // 各向き間の辺を張る
    REP(ind, masu) {
        FOR(i, 0, 4) {
            FOR(j, i + 1, 4) {
                dj.makeEdge(masu*i + ind, masu*j + ind, 1);
                dj.makeEdge(masu*j + ind, masu*i + ind, 1);
            }
        }
    }
    int s, t;
    s = masu*4; // start node
    t = masu*4 + 1; // goal node
    // s -> startnodeにcost0で辺を貼る
    FOR(i, 0, 4) dj.makeEdge(s, masu * i + (w * r1) + c1, 0);
    // goalnode -> tにcost0で辺を張る
    FOR(i, 0, 4) dj.makeEdge(masu * i + (w * r2) + c2, t, 0);
    int nh, nw;
    // 0:up, 1: right, 2:down, 3:left の レイヤだとする
    REP(hh, h){
        REP(ww, w){
            // 上にマスがあり && 上が"."なら、 cost0で辺を張る
            nh = hh - 1; nw = ww;
            if(0 <= nh && nh < h && 0 <= nw && nw < w && maze[w*nh+nw] == '.') dj.makeEdge(masu*0 + w * hh + ww, masu*0 + w * nh + nw, 0);
            nh = hh; nw = ww + 1;
            if(0 <= nh && nh < h && 0 <= nw && nw < w && maze[w*nh+nw] == '.') dj.makeEdge(masu*1 + w * hh + ww, masu*1 + w * nh + nw, 0);
            nh = hh + 1; nw = ww;
            if(0 <= nh && nh < h && 0 <= nw && nw < w && maze[w*nh+nw] == '.') dj.makeEdge(masu*2 + w * hh + ww, masu*2 + w * nh + nw, 0);
            nh = hh; nw = ww - 1;
            if(0 <= nh && nh < h && 0 <= nw && nw < w && maze[w*nh+nw] == '.') dj.makeEdge(masu*3 + w * hh + ww, masu*3 + w * nh + nw, 0);
        }
    }
    // s->tでダイクストラする
    dj.solve(s, t);
    // 制約上、この問題ではunreachはないが一応。
    if(dj.cost[t] == dj.INF) cout << -1 << "\n";
    else cout << dj.cost[t] << "\n";
}