BZOJ 3205 - [Apio2013]机器人

#动态规划 #最短路
Published on 2017-05-11

题目地址

描述

VRI（Voltron 机器人学会）的工程师建造了 n(n≤9)n(n\le 9) 个机器人。任意两个兼容的机器人站在同一个格子时可以合并为一个复合机器人。

我们把机器人用 11 至 nn 编号。如果两个机器人的编号是连续的，那么它们是兼容的，可以合并成一个复合机器人。最初这 nn 个机器人各自都只有唯一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号，分别是构成它的所有机器人中最小和最大的编号。

例如，22 号机器人只可以与 11 号或 33 号机器人合并。若 22 号机器人与 33 号机器人合并，可构成编号为 的复合机器人。如果编号为 的复合机器人与编号为 的复合机器人合并，可构成编号为 的复合机器人。当所有机器人合并以后则构成 复合机器人。

工程师把这 nn 个机器人放在了一个封闭的房间中，房间四周均是墙。该房间被划分成 w×h(w,h≤500)w\times h(w, h\le 500) 个方格。有些方格有障碍物，机器人不可经过或停留；其余方格允许多个机器人停留，同时允许机器人经过。任何时候一个机器人只占用一个方格。初始时刻,所有机器人均在不同的方格中。

这些原始的机器人不会自发地移动。它们只有被工程师沿 xx 轴或 yy 轴推动后，才会沿推动的方向不断向前直线移动，直至碰到障碍物或墙停止移动。停止移动后，它会扫描当前的格子是否存在可以与它合并的机器人，如果有，则合并并继续检查，直至不能再合并为止。工程师只能沿水平向左、水平向右、竖直向上、竖直向下四个方向推动机器人，并且，在机器人尚未停止移动时，不允许推动其它机器人，因此任何时刻，房间中都只能有一个机器人移动。

为了帮助机器人转向，工程师在一些格子中放置了转向器。具体地说，转向器分为顺时针转向器（右转器）和逆时针转向器（左转器），顺时针转向器可以使到达该格子的机器人沿顺时针方向转向 90∘90^{\circ}；逆时针转向器可以使到达该格子的机器人沿逆时针方向转向 90∘90^{\circ}。

现在，我们将告诉你初始时刻房间内的信息。请你计算工程师最少共计需要推动机器人多少次，才能把所有的 nn 个机器人全部合并（如果可能的话）。

分析

本题涉及连续标号的合并，所以很容易得到有一个区间 DP 的模型：设 dp(i,j,x,y)dp(i, j, x, y) 为将标号 [i,j)[i, j) 的机器人合并到 (x,y)(x, y) 的最小代价。

转移分为两种，可以原地合并机器人，也可以往四个方向走。我们利用记忆化 DFS 预处理出每个位置向 4 个方向走，最后到达的位置，注意处理存在环的情况。

dp(i,j,x,y)=mini<k<jdp(i,k,x,y)+dp(k,j,x,y)dp(i,j,a,b)←dp(i,j,x,y)+1,(x,y)can reach(a,b) \begin{aligned} dp(i, j, x, y) & = \min_{i< k< j}dp(i, k, x, y) + dp(k, j, x, y)\\ dp(i, j, a, b) &\leftarrow dp(i, j, x, y) + 1,\qquad (x, y)\;\text{can reach}\;(a, b) \end{aligned}

对于第一种转移，与普通的区间 DP 没有区别，可以直接转移，总复杂度为 O(n3wh)O(n^3wh)。而第二种转移则涉及到同层的转移，与斯坦纳树的 DP 思想类似，对每个 (i,j)(i, j)，先做完第一种转移，对于第二种转移，使用 SPFA／Dijkstra 做多源最短路来完成转移。这里采用 Dijkstra 算法：把每个格子都加入优先队列，然后每次取出最小的值来更新其他格子。边数是 O(4wh)O(4wh) 的，所以复杂度是 O(whlogwh)O(wh\log{wh})，由于常数较大，这样的复杂度不足以通过极限数据。

注意到每条边的权值都是 11，我们可以利用这个性质来优化掉优先队列。用计数排序 O(wh)O(wh) 将每个格子的 DP 值从小到大排序，加入第一个队列。由于 Dijkstra 算法每次取出的距离是单调不降的，而且边权都是 11，所以我们可以将每次更新的节点加入第二个队列，则第二个队列的距离也是单调不降的。每次取优先队列的最小值，变为从两个队列首取一个较小值，这样就能去掉优先队列，将一次多源最短路的时间降为 O(wh)O(wh)。

总复杂度：O(n3wh)O(n^3wh)。

代码

//  Created by Sengxian on 2017/05/09.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 3205 动态规划
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 9, MAX_H = 500 + 3, MAX_W = 500 + 3, INF = 0x3f3f3f3f;
int n, h, w, dp[MAX_N][MAX_N + 1][MAX_H][MAX_W];
char grid[MAX_H][MAX_W];
pair<int, int> des[MAX_H][MAX_W][4];
bool vis[MAX_H][MAX_W][4];

inline bool check(int i, int j) {
    return i >= 0 && i < h && j >= 0 && j < w && grid[i][j] != 'x';
}

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

pair<int, int> dfs(int x, int y, int d) {
    if (vis[x][y][d]) return des[x][y][d];
    vis[x][y][d] = true;

    int _d = d;
    if (grid[x][y] == 'C') _d = (d + 1) % 4;
    else if (grid[x][y] == 'A') _d = (d + 3) % 4;

    int _x = x + dx[_d], _y = y + dy[_d];
    if (check(_x, _y)) return des[x][y][d] = dfs(_x, _y, _d);
    return des[x][y][d] = make_pair(x, y);
}

void prepare() {
    memset(des, -1, sizeof des);
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            for (int k = 0; k < 4; ++k) if (grid[i][j] != 'x')
                des[i][j][k] = dfs(i, j, k);
}

void print(pair<int, int> x) {
    cout << x.first << ' ' << x.second << endl;
}

inline bool relax(int &a, const int &b) {
    return b < a ? (a = b, true) : false;
}

int ii, jj;

inline bool cmp(const pair<int, int> &lhs, const pair<int, int> &rhs) {
    return dp[ii][jj][lhs.first][lhs.second] < dp[ii][jj][rhs.first][rhs.second];
}

void spfa(int i, int j) {
    static pair<int, int> q1[MAX_H * MAX_W], q2[MAX_H * MAX_W * 4];
    static bool vis[MAX_H][MAX_W];

    int l1 = 0, r1 = 0, l2 = 0, r2 = 0;
    memset(vis, 0, sizeof vis);
    for (int x = 0; x < h; ++x)
        for (int y = 0; y < w; ++y) if (dp[i][j][x][y] < INF)
            q1[r1++] = make_pair(x, y);
    ii = i, jj = j, sort(q1, q1 + r1, cmp);

    while (r1 - l1 >= 1 || r2 - l2 >= 1) {
        pair<int, int> now;
        if (r1 - l1 >= 1 && r2 - l2 >= 1) {
            if (cmp(q1[l1], q2[l2])) now = q1[l1++];
            else now = q2[l2++];
        } else if (r1 - l1 >= 1) now = q1[l1++];
        else now = q2[l2++];
        if (vis[now.first][now.second]) continue;
        vis[now.first][now.second] = true;
        for (int d = 0; d < 4; ++d) {
            pair<int, int> ne = des[now.first][now.second][d];
            if (ne.first != -1 && relax(dp[i][j][ne.first][ne.second], dp[i][j][now.first][now.second] + 1))
                q2[r2++] = ne;
        }
    }
}

void solve() {
    for (int l = 1; l <= n; ++l)
        for (int i = 0; i + l <= n; ++i) {
            int j = i + l;
            for (int x = 0; x < h; ++x)
                for (int k = i + 1; k < j; ++k)
                    for (int y = 0; y < w; ++y)
                        relax(dp[i][j][x][y], dp[i][k][x][y] + dp[k][j][x][y]);
            spfa(i, j);
        }

    int ans = INF;
    for (int x = 0; x < h; ++x)
        for (int y = 0; y < w; ++y)
            relax(ans, dp[0][n][x][y]);
    printf("%d\n", ans == INF ? -1 : ans);
}

int main() {
#ifdef DEBUG
    freopen("test.in", "r", stdin);
#endif
    n = readInt(), w = readInt(), h = readInt();
    memset(dp, 0x3f, sizeof dp);
    for (int i = 0; i < h; ++i) {
        scanf("%s", grid[i]);
        for (int j = 0; j < w; ++j)
            if (isdigit(grid[i][j])) {
                int num = grid[i][j] - '1';
                dp[num][num + 1][i][j] = 0;
            }
    }

    prepare();
    solve();    

    return 0;
}
HDOJ 5822 - color