ICPC国内予選2005年 F問題 : Cleaning Robot

問題. Cleaning Robot

サイズが横幅 ・縦幅 の部屋がある．部屋のタイル上に1つの掃除ロボットといくつかの障害物が置かれており，各タイルは綺麗か汚れている．掃除ロボットは上下左右の障害物の無いタイルへ移動することができる．すべてのタイルを綺麗にするために移動する最小距離を求めよ．

制約： ，　汚れたタイルの数

解法1. 幅優先探索 + 全探索

頂点集合がロボットの初期座標と汚れたタイルの座標の集合となる完全グラフ を作成する．このとき，各辺の重みは座標間の最短距離として幅優先探索で求める．もし，ある2頂点間が移動不可能ならばすべてのタイルを綺麗にすることができないので終了する．
問題の答えは 上でロボットの初期座標を始点とする重み和最小のハミルトン路である．ハミルトン路とはすべての頂点を訪れるパスのことである．今回は，頂点数が高々10なのでパスを全探索して重み和最小のものを見つける．全探索の実装はnext_permutationを用いた．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using Graph = vector<vector<int>>;

int MinimumPath(const Graph &g) {
    const int n = g.size();
    int min_d = 1e8;

    vector<int> idx(n - 1);
    iota(idx.begin(), idx.end(), 1);

    do {
        int d = g[0][idx[0]];
        for (int i = 0; i < n - 2; ++i) d += g[idx[i]][idx[i + 1]];
        min_d = min(min_d, d);
    } while (next_permutation(idx.begin(), idx.end()));

    return min_d;
}

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};

int Distance(const auto &src, const auto &dst, const int h, const int w, const vector<string> &c) {
    vector<vector<int>> d(h, vector<int>(w, -1));
    queue<pair<int, int>> que;
    que.push(src);
    d[src.first][src.second] = 0;

    while (!que.empty()) {
        auto cur = que.front(); que.pop();

        for (int dir = 0; dir < 4; ++dir) {
            pair<int, int> nxt(cur.first + dr[dir], cur.second + dc[dir]);
            if (nxt.first < 0 || nxt.second < 0 || h <= nxt.first || w <= nxt.second
                || d[nxt.first][nxt.second] != -1 || c[nxt.first][nxt.second] == 'x')
                continue;
            d[nxt.first][nxt.second] = d[cur.first][cur.second] + 1;
            que.push(nxt);
        }
    }

    return d[dst.first][dst.second];
}

pair<bool, Graph> MakeGraph(const int w, const int h, const vector<string> &c) {
    vector<pair<int, int>> pos(1);
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            if (c[i][j] == 'o') pos[0] = make_pair(i, j);
            else if (c[i][j] == '*') pos.emplace_back(make_pair(i, j));
        }

    const int n = pos.size();
    Graph d(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            int d_ij = Distance(pos[i], pos[j], h, w, c);
            if (d_ij == -1) return make_pair(true, d);
            d[i][j] = d[j][i] = d_ij;
        }

    return make_pair(false, d);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int w, h;

    while (cin >> w >> h, (w != 0 || h != 0)) {
        vector<string> c(h);
        for (auto &x : c) cin >> x;

        auto res = MakeGraph(w, h, c);
        if (res.first) cout << -1 << '\n';
        else cout << MinimumPath(res.second) << '\n';
    }

    return 0;
}

解法2. 幅優先探索 + Bit DP

解法1の完全グラフを作成するところまでは一緒である．異なるのは重み和最小のハミルトン路を見つけるところである．もし，掃除ロボットが最初の位置に戻ってくるとしたら巡回セールスマン問題(Traveling Salesman Problem; TSP)となる．TSPを解く現在知られている高速な厳密解法として部分集合上動的計画法(dynamic programming over subsets)がある．競プロの世界では部分集合をbitで持つことからBit DP [1]と呼ばれている．今回の問題は始点が決まっていて閉路である必要がないのでTSPの解法を修正して解いている．

計算時間：

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using Graph = vector<vector<int>>;

int TravelingSalesman(const Graph &g) {
    const int n = g.size(), INF = n * n * n;
    vector<vector<int>> dp(1 << n, vector<int>(n, INF));
    dp[1][0] = 0;

    for (int s = 1; s < 1 << n; ++s) {
        for (int cur = 0; cur < n; ++cur) {
            if (!(s >> cur & 1) || INF <= dp[s][cur]) continue;

            for (int dst = 0; dst < n; ++dst) {
                if (dst != cur && !(s >> dst & 1))
                    dp[s | 1 << dst][dst] = min(dp[s | 1 << dst][dst], dp[s][cur] + g[cur][dst]);
            }
        }
    }

    return *min_element(dp[(1 << n) - 1].begin(), dp[(1 << n) - 1].end());
}

const int dr[] = {-1, 0, 1, 0};
const int dc[] = {0, -1, 0, 1};

int Distance(const auto &src, const auto &dst, const int h, const int w, const vector<string> &c) {
    vector<vector<int>> d(h, vector<int>(w, -1));
    queue<pair<int, int>> que;
    que.push(src);
    d[src.first][src.second] = 0;

    while (!que.empty()) {
        auto cur = que.front(); que.pop();

        for (int dir = 0; dir < 4; ++dir) {
            pair<int, int> nxt(cur.first + dr[dir], cur.second + dc[dir]);
            if (nxt.first < 0 || nxt.second < 0 || h <= nxt.first || w <= nxt.second
                || d[nxt.first][nxt.second] != -1 || c[nxt.first][nxt.second] == 'x')
                continue;
            d[nxt.first][nxt.second] = d[cur.first][cur.second] + 1;
            que.push(nxt);
        }
    }

    return d[dst.first][dst.second];
}

pair<bool, Graph> MakeGraph(const int w, const int h, const vector<string> &c) {
    vector<pair<int, int>> pos(1);
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j) {
            if (c[i][j] == 'o') pos[0] = make_pair(i, j);
            else if (c[i][j] == '*') pos.emplace_back(make_pair(i, j));
        }

    const int n = pos.size();
    Graph d(n, vector<int>(n));
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j) {
            int d_ij = Distance(pos[i], pos[j], h, w, c);
            if (d_ij == -1) return make_pair(true, d);
            d[i][j] = d[j][i] = d_ij;
        }

    return make_pair(false, d);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int w, h;

    while (cin >> w >> h, (w != 0 || h != 0)) {
        vector<string> c(h);
        for (auto &x : c) cin >> x;

        auto res = MakeGraph(w, h, c);
        if (res.first) cout << -1 << '\n';
        else cout << TravelingSalesman(res.second) << '\n';
    }

    return 0;
}

まとめ

TSPはNP困難です．

参考文献

[1] プログラミングコンテストでの動的計画法