AOJ 1178: A Broken Door - Lilliput Steps

概要

日本語なので略。

解法

迷路の各部屋ごとに、「隣接したドアが壊れた場合のゴールへ到達するのに必要なカードの個数」を求める。もし、隣接するドアが複数ある場合は、そのなかの最大値を求める。このステップは $O(hw)$ 個の部屋それぞれに対して幅優先探索を行えば良いので、 $O(h^2w^2)$ 時間で実行することが可能である。

先程求めた情報を元に、解の二分探索を行う。すなわち、「スタートから、どのドアが壊れてもカードの枚数が $k$ 枚以下で迷路を突破できるか？」という問題が解ければ良い。これも幅優先探索で確認できるが、隣の部屋との間に壁がない場合でも、「スタートから現在の部屋までに使ったカードの枚数＋ 1 (隣の部屋への移動分) + 隣の部屋で扉が壊れた場合にゴールへたどり着くために必要なカードの個数」が $k$ より大きくなった場合、遷移をしないようにする必要がある。このステップの計算量は $O(hw \log hw)$ となる。

よって、 $O(h^2w^2)$ 時間でこの問題が解けた。

コード

#include <bits/stdc++.h>

using namespace std;

int dist[128][128], dist2[128][128], cost[128][128];
int dy[] = {0, 1, 0, -1}, dx[] = {1, 0, -1, 0};
int mp[128][128];

void bfs(int sy, int sx, int dist[][128])
{
    queue<pair<int, int>> q;
    q.push(make_pair(sy, sx));

    for (int i = 0; i < 128; i++){
        fill(dist[i], dist[i] + 128, 1000000000);
    }

    dist[sy][sx] = 0;

    while (q.size()){
        pair<int, int> x = q.front(); q.pop();

        for (int i = 0; i < 4; i++){
            pair<int, int> nx = make_pair(x.first + dy[i], x.second + dx[i]);
            if (nx == make_pair(sy, sx) || dist[nx.first][nx.second] != 1000000000) continue;
            if (!mp[nx.first][nx.second]){
                dist[nx.first][nx.second] = dist[x.first][x.second] + 1;
                q.push(nx);
            }
        }
    }
}

bool ok(int m, int h, int w)
{
    int c[128][128];

    for (int i = 0; i < 128; i++) fill(c[i], c[i] + 128, 1000000000);

    queue<pair<int, int>> q;
    q.push(make_pair(1, 1));
    c[1][1] = 0;

    while (q.size()){
        pair<int, int> x = q.front(); q.pop();

        for (int i = 0; i < 4; i++){
            pair<int, int> nx = make_pair(x.first + dy[i], x.second + dx[i]);
            if (mp[nx.first][nx.second]) continue;
            if (nx == make_pair(1, 1) || c[nx.first][nx.second] != 1000000000) continue;
            if (c[x.first][x.second] + 1 + cost[nx.first][nx.second] <= 2 * m){
                c[nx.first][nx.second] = c[x.first][x.second] + 1;
                q.push(nx);
            }
        }
    }

    return (c[2 * h - 1][2 * w - 1] <= 2 * m);
}

int main()
{
    int h, w;

    while (scanf("%d %d", &h, &w) && h){
        memset(mp, 0, sizeof(mp));
        for (int i = 0; i < 2 * h + 1; i++){
            for (int j = 0; j < 2 * w + 1; j++){
                mp[i][j] = !((i % 2) && (j % 2));
            }
        }

        for (int i = 1; i < 2 * h; i++){
            for (int j = 0; j < w - (i % 2); j++){
                scanf("%d", &mp[i][2 * j + 1 + (i % 2)]);
            }
        }

        bfs(1, 1, dist);

        if (dist[2 * h - 1][2 * w - 1] == 0){
            printf("-1\n");
            continue;
        }

        memset(cost, 0, sizeof(cost));

        for (int i = 1; i < 2 * h; i++){
            for (int j = 0; j < w - (i % 2); j++){
                int ny = i, nx = 2 * j + 1 + (i % 2);
                if (mp[ny][nx]) continue;
                mp[ny][nx] = 1;
                if (i % 2){
                    bfs(ny, nx - 1, dist2);
                    cost[ny][nx - 1] = max(cost[ny][nx - 1], dist2[2 * h - 1][2 * w - 1]);
                    bfs(ny, nx + 1, dist2);
                    cost[ny][nx + 1] = max(cost[ny][nx + 1], dist2[2 * h - 1][2 * w - 1]);
                }
                else {
                    bfs(ny - 1, nx, dist2);
                    cost[ny - 1][nx] = max(cost[ny - 1][nx], dist2[2 * h - 1][2 * w - 1]);
                    bfs(ny + 1, nx, dist2);
                    cost[ny + 1][nx] = max(cost[ny + 1][nx], dist2[2 * h - 1][2 * w - 1]);
                }
                mp[ny][nx] = 0;
            }
        }

        int l = 0, r = 2 * h * w + 1;

        while (l != r){
            int mid = (l + r) / 2;

            if (ok(mid, h, w)) r = mid;
            else l = mid + 1;
        }

        printf("%d\n", l > 2 * h * w ? -1 : l);
    }
}