题目地址：洛谷：【P3638】[APIO2013]机器人 – 洛谷、BZOJ：Problem 3205. — [Apio2013]机器人

题目描述

VRI（Voltron 机器人学会）的工程师建造了 n 个机器人。任意两个兼容的机 器人站在同一个格子时可以合并为一个复合机器人。
我们把机器人用 1 至 n 编号（n ≤ 9）。如果两个机器人的编号是连续的，那 么它们是兼容的，可以合并成一个复合机器人。最初这 n 个机器人各自都只有唯 一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号， 分别是构成它的所有机器人中最小和最大的编号。
例如，2 号机器人只可以与 1 号或 3 号机器人合并。若 2 号机器人与 3 号机 器人合并，可构成编号为 2-3 的复合机器人。如果编号为 2-3 的复合机器人与编 号为 4-6 的复合机器人合并，可构成编号为 2-6 的复合机器人。当所有机器人合 并以后则构成 1-n 复合机器人。
工程师把这 n 个机器人放在了一个封闭的房间中，房间四周均是墙。该房间 被划分成 w × h 个方格。有些方格有障碍物，机器人不可经过或停留；其余方格 允许多个机器人停留，同时允许机器人经过。任何时候一个机器人只占用一个方 格。初始时刻，所有机器人均在不同的方格中。
这些原始的机器人不会自发地移动。它们只有被工程师沿 x 轴或 y 轴推动 后，才会沿推动的方向不断向前直线移动，直至碰到障碍物或墙停止移动。停止 移动后，它会扫描当前的格子是否存在可以与它合并的机器人，如果有，则合并 并继续检查，直至不能再合并为止。工程师只能沿水平向左、水平向右、竖直向 上、竖直向下四个方向推动机器人，并且，在机器人尚未停止移动时，不允许推 动其它机器人，因此任何时刻，房间中都只能有一个机器人移动。
为了帮助机器人转向，工程师在一些格子中放置了转向器。具体地说，转向 器分为顺时针转向器（右转器）和逆时针转向器（左转器），顺时针转向器可以 使到达该格子的机器人沿顺时针方向转向 90°；逆时针转向器可以使到达该格 子的机器人沿逆时针方向转向 90°。
现在，我们将告诉你初始时刻房间内的信息。请你计算工程师最少共计需要 推动机器人多少次，才能把所有的 n 个机器人全部合并（如果可能的话）。

输入输出格式

输入格式：
你的程序必须从标准输入读入。
输入的第 1 行包含 3 个整数 n、w 和 h，用 空格隔开。
输入文件中接下来的 h 行描述初始时刻房间内的信息，每行包含 w 个字符。 这 w × h 个字符中每一个表示房间中的一个格子，意义如下：
‘1’至‘9’：表示该方格中有一个机器人，编号为这个数字；
‘x’：表示该方格有障碍物；
‘A’：表示该方格中有一个逆时针转向器；
‘C’：表示该方格中有一个顺时针转向器；
‘.’：表示该方格为空地。

输出格式：
你的程序必须输出到标准输出。输出仅一个整数，表示最少需要推动的次数。 若不能使所有机器人全部合并，输出-1。

输入输出样例

输入样例#1：

4 10 5 
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...

输出样例#1：

5

说明

第一步：向右推动 3 号机器人，当它碰到转向器后会向上继续移动，直至碰 到墙壁停止移动。
第二步：向上推动 4 号机器人，当它碰到墙壁后停止移动，与 3 号机器人合 并，构成 3-4 号机器人
第三步：向上推动 2 号机器人，当它碰到转向器后会向左移动，由于左侧为 墙壁，故停留在原地。
第四步：向右推动 2 号机器人，由于它在一个转向器上，故它会向上移动， 直至碰到墙壁停止移动，与 1 号机器人合并，构成 1-2 号机器人。
第五步：向左推动 3-4 号机器人，当它碰到墙壁后停止移动，与 1-2 号机器 人合并，构成 1-4 号机器人。
我们将使用以下 4 类输入测例测试你的程序。

1. （10 分）测例满足 n = 2，w ≤ 10 且 h ≤ 10，没有任何转向器。
2. （20 分）测例满足 n = 2，w ≤ 10 且 h ≤ 10。
3. （30 分）测例满足 n ≤ 9，w ≤ 300 且 h ≤ 300。
4. （40 分）测例满足 n ≤ 9，w ≤ 500 且 h ≤ 500。

题解

首先这是一个斯坦纳树的模型，但是比较棘手的是细节部分。
首先在斯坦纳树问题中的边在这里变成了从一个点向某个方向走最终能到达哪里这样的一个问题，就需要用记忆化搜索预处理出这个。而这个DFS细节又比较多，比较难写。
然后我们设计DP状态dp[l][r][i][j]表示在点(i, j)将编号为[l, r]的机器人组合在一起所需的最少推动次数。斯坦纳树问题的第一种转移在这里变成了一个区间DP的套路，方程如下
dp[l][r][i][j] = \min_{k \in [l, r]} \{ dp[l][k][i][j] + dp[k + 1][r][i][j] \}
而第二种转移仍然是从这个点到向某个方向推的下一个点
dp[l][r][i][j] = \min \{ dp[l][r][i'][j'] + 1 \}
第二种转移依旧要依赖于SPFA来做，可是SPFA的复杂度不靠谱，我们考虑优化成下面的形式。
我们把SPFA的出发点集合按dp值先排个序。由于dp值不会很大，可以采用计数排序，实现O(n)的排序。把排序后的点扔进队列Q1，然后把扩展出来的点扔进队列Q2。每次要松弛的时候从两个队列的队首拿dp值最小的来松弛。这种优化方法只有当图的边权全部为1的时候才能用。
答案就是\min \{ dp[1][n][i][j] \} 。
吐槽：洛谷上这个题卡常的厉害，我优化成底下这个代码的样子还没过，最后开了O2苟过去的。

代码

题解代码参考并借鉴了[APIO2013] – FallDream – 博客园中的写法，感谢原作者。

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

inline bool ismap(register char c) {
    return c == 'A' || c == 'C' || c == '.' || c == 'x' || (c > '0' && c <= '9');
}

inline char readmap() {
    register char c;
    while(!ismap(c = fgc()));
    return c;
}

const int MAXK = 10, MAXN = 505, INF = 0x3f3f3f3f;
const int fix[2][4] = {{-1, 0, 1, 0}, {0, 1, 0, -1}};

int k, n, m, clk, top; 
int dp[MAXK][MAXK][MAXN][MAXN], vis[MAXN][MAXN][4], v[200005], rk[200005];
char mmp[MAXN][MAXN];
bool inque[MAXN][MAXN];

struct Point {
    int x, y;
} pts[MAXK], nxt[MAXN][MAXN][4], q[250005];

struct Queue {
    Point q[250005];
    static const int len = 250000;
    int l, r;
    Queue() {
        l = r = 0;
    }
    inline void clear() {
        l = r = 0;
    }
    inline void push(Point p) {
        q[r++] = p;
        if(r > len) r -= len;
    }
    inline Point front() {
        return q[l];
    }
    inline void pop() {
        l++;
        if(l > len) l -= len;
    }
    inline bool empty() {
        return l == r;
    }
}; 

Queue q1, q2;

inline Point dfs(int x, int y, int dir) {
    if(vis[x][y][dir] == clk) {
        nxt[x][y][dir].x = nxt[x][y][dir].y = -1; 
        return nxt[x][y][dir];
    }
    vis[x][y][dir] = clk;
    if(nxt[x][y][dir].x && nxt[x][y][dir].y) return nxt[x][y][dir];
    register int ndir = dir;
    if(mmp[x][y] == 'A') ndir = dir + 3;
    else if(mmp[x][y] == 'C') ndir = dir + 1;
    if(ndir >= 4) ndir -= 4;
    register int nx = x + fix[0][ndir], ny = y + fix[1][ndir];
    if(nx < 1 || nx > n || ny < 1 || ny > m || mmp[nx][ny] == 'x') {
        nxt[x][y][dir].x = x;
        nxt[x][y][dir].y = y;
        return nxt[x][y][dir];
    }
    return nxt[x][y][dir] = dfs(nx, ny, ndir);
}

inline void spfa(register int l, register int r) {
    // 计数排序
    memset(v, 0, sizeof(v));
    register int mx = 0;
    for(register int i = 1; i <= top; i++) {
        if(mx < dp[l][r][q[i].x][q[i].y]) mx = dp[l][r][q[i].x][q[i].y];
        v[dp[l][r][q[i].x][q[i].y]]++;
    }
    for(register int i = 1; i <= mx; i++) v[i] += v[i - 1];
    for(register int i = 1; i <= top; i++) rk[v[dp[l][r][q[i].x][q[i].y]]--] = i;
    for(register int i = 1; i <= top; i++) q1.push(q[rk[i]]);
    top = 0;
    // SPFA
    while(!q1.empty() || !q2.empty()) {
        Point t;
        if(q1.empty() || (!q2.empty() && dp[l][r][q1.front().x][q1.front().y] > dp[l][r][q2.front().x][q2.front().y])) {
            t = q2.front(); q2.pop();
        } else {
            t = q1.front(); q1.pop();
        }
        inque[t.x][t.y] = false;
        for(register int i = 0; i < 4; i++) {
            Point nx = nxt[t.x][t.y][i];
            if(nx.x == -1 || nx.y == -1) continue;
            if(dp[l][r][nx.x][nx.y] > dp[l][r][t.x][t.y] + 1) {
                dp[l][r][nx.x][nx.y] = dp[l][r][t.x][t.y] + 1;
                if(!inque[nx.x][nx.y]) {
                    inque[nx.x][nx.y] = true;
                    q2.push(nx);
                }
            }
        }
    }
}

int main() {
    k = readint(); m = readint(); n = readint();
    for(register int i = 1; i <= n; i++) {
        for(register int j = 1; j <= m; j++) {
            mmp[i][j] = readmap();
            if(mmp[i][j] > '0' && mmp[i][j] <= '9') {
                int t = mmp[i][j] - '0';
                pts[t].x = i;
                pts[t].y = j;
            }
        }
    }
    for(register int i = 1; i <= n; i++) {
        for(register int j = 1; j <= m; j++) {
            if(mmp[i][j] != 'x') {
                for(register int k = 0; k < 4; k++) {
                    clk++;
                    dfs(i, j, k);
                }
            }
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    for(register int i = 1; i <= k; i++) {
        inque[pts[i].x][pts[i].y] = true;
        q[++top] = pts[i];
        dp[i][i][pts[i].x][pts[i].y] = 0;
        spfa(i, i);
    }
    for(register int len = 2; len <= k; len++) {
        for(register int l = 1; l + len - 1 <= k; l++) {
            register int r = l + len - 1;
            for(register int i = 1; i <= n; i++) {
                for(register int j = 1; j <= m; j++) {
                    for(register int k = l; k < r; k++) {
                        if(dp[l][r][i][j] > dp[l][k][i][j] + dp[k + 1][r][i][j]) {
                            dp[l][r][i][j] = dp[l][k][i][j] + dp[k + 1][r][i][j];
                        }
                    }
                    if(dp[l][r][i][j] < INF) {
                        q[++top].x = i;
                        q[top].y = j;
                        inque[i][j] = true;
                    }
                }
            }
            spfa(l, r);
        }
    }
    register int ans = INF;
    for(register int i = 1; i <= n; i++) {
        for(register int j = 1; j <= m; j++) {
            if(ans > dp[1][k][i][j]) ans = dp[1][k][i][j];
        }
    }
    if(ans == INF) {
        puts("-1");
    } else {
        printf("%d", ans);
    }
    return 0;
}