けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 3055 こたつがめを燃やさないで (RUPC 2019 day2-E)

AOJ RUPC 迷路 二次元グリッド 最短路問題 DP 盤面を予め変更する 最適化テク:固定する変数を入れ替えて考える 最小コスト 魔法を唱える問題 DP状態:向き 【問題集】最短路問題 典型要素を詰め合わせた教育的問題 壁マス 最適化問題

こういうの超苦手系だけど、苦手なりに解法を詰められたのは成長の証で嬉しい！

olphe さん、ナンさんとチームを組んでいて、olphe さんに考察を話して、詰めてくれて、爆弾周りの見落としがあって詰まって、みんなでデバッグして...とチーム戦ならではの考察&実装&デバッグプレイを楽しめた！！！！！！！！
チームメンバーに感謝。

問題へのリンク

問題概用

H × W のグリッドが与えられ、スタートからゴールへ進みたい。スタート / ゴール以外のマスの属性は

  • 通路： "." で表され、任意に通れる
  • 壁： "#" で表され、デフォルトでは通れないが、「魔法」を唱えることで通路になって通れるようになる
  • 爆弾： "*" で表され、任意に通れる。爆弾の近くでは「魔法」を唱えることはできない

となっている。魔法は

  • 今いるマスおよび周囲の 8 マスに「爆弾」があったら「魔法」を使えない
  • 「魔法」を使うと周囲 8 マス内に存在する「壁」をすべて破壊して「通路」に変えてしまうことができる

1 マス移動するのに A コスト、魔法を 1 回唱えるのに B コストかかるとする。スタートからゴールまでに要する最小コストを求めよ。

制約

  • H, W \le 3000

考えたこと

いわゆる、スタートからゴールまで行く系の問題で、盤面に操作したりもできる系！！！

こういうのは一見「えっ！？」となってしまうのだけど、一つ考えるべきこととして

  • スタートからゴールまでの経路を 1 つ固定したときに、最小で何回の盤面操作コストで行けるか

を考えることな気がする。この手の問題に限らず、複数の要因の絡み合う最適化問題では一方を固定してどうなるかを考えるのが良さそう。Magic だって、最初に宝箱を開ける順番を固定したときのマジシャンの最適戦略を考えるのが良かった。

さて、今回の問題もとりあえず経路を固定してみる。そうすると

  • 直進しているときは、壁が登場するたびに魔法を 1 回ずつ唱えることになる

  • 曲がるときだけ注意が必要で、あるマスにいるときに「次に進むマス」と「そこから左右に曲がったマス」との両方に壁があるときは 2 つまとめて壊せる

ということが見て取れる。よって、DP をしているときに

  • 曲がろうとしているかを状態にもつ
  • 曲がるという遷移も追加してしまう

という風な解法がいい感じ。今回は後者の「曲がる遷移も予め追加してしまう」というのがバッチリはまる。

以上まとめて、

  • dp[ x ][ y ] := そのマスにいたる最小コスト

として

  • 進む方向を四方それぞれ考えて、
  • 進む方向が通路なら何も考えずに A の辺
  • 進む方向が壁なら
    • 今いるマスと周囲 8 マスに爆弾があったら何もしない
    • 爆弾がなかったら、進むマスに A+B の辺
    • 進むマスとその「左」「右」それぞれにも壁があるなら、そのそれぞれに 2A+B の辺

を貼って最短路問題を解けば OK

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;
using pint = pair<int,int>;
const int INF = 1<<29;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
bool chmin(int &a, int b) { if (a > b) {a = b; return true;} return false; }

int H, W, A, B;
vector<string> fi;

int main() {
    cin >> H >> W >> A >> B;
    fi.resize(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    int sx, sy, tx, ty;
    for (int i = 0; i < H; ++i) for (int j = 0; j < W; ++j) {
            if (fi[i][j] == 's') sx = i, sy = j;
            if (fi[i][j] == 'g') tx = i, ty = j;
        }
    
    priority_queue<pair<int,pint>, vector<pair<int,pint> >,
                   greater<pair<int,pint> > > que;
    que.push({0, pint(sx, sy)});
    vector<vector<int> > dp(H, vector<int>(W, INF));
    dp[sx][sy] = 0;
    while (!que.empty()) {
        auto cur = que.top(); que.pop();
        int cur_dist = cur.first;
        int x = cur.second.first;
        int y = cur.second.second;
        if (cur_dist > dp[x][y]) continue;

        // 通常の移動
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (fi[nx][ny] == '#') continue;
            if (chmin(dp[nx][ny], dp[x][y] + A)) que.push({dp[nx][ny], pint(nx, ny)});
        }

        // 魔法
        bool can = true;
        for (int i = x-1; i <= x+1; ++i)
            for (int j = y-1; j <= y+1; ++j) {
                if (i < 0 || i >= H || j < 0 || j >= W) continue;
                if (fi[i][j] == '*') can = false;
            }
        if (can) {
            for (int i = x-1; i <= x+1; ++i)
                for (int j = y-1; j <= y+1; ++j) {
                    if (i < 0 || i >= H || j < 0 || j >= W) continue;
                    if (i == x && j == y) continue;
                    if (fi[i][j] != '#') continue;
                    if (chmin(dp[i][j], dp[x][y] + B + A * (abs(i-x) + abs(j-y))))
                        que.push({dp[i][j], pint(i, j)});
                }       
        }
    }
    if (dp[tx][ty] < INF) cout << dp[tx][ty] << endl;
    else cout << "INF" << endl;
}