洛谷P3638 [APIO2013] 机器人题解

题目链接：P3638 [APIO2013] 机器人

题意：

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

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

例如，$2$ 号机器人只可以与 $1$ 号或 $3$ 号机器人合并。若 $2$ 号机器人与 $3$ 号机器人合并，可构成编号为 $2\sim 3$ 的复合机器人。如果编号为 $2\sim 3$ 的复合机器人与编号为 $4\sim 6$ 的复合机器人合并，可构成编号为 $2\sim 6$ 的复合机器人。当所有机器人合并以后则构成 $1\sim n$ 复合机器人。

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

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

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

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

输入格式：

输入的第 $1$ 行包含 $3$ 个整数 $n,w$ 和 $h$，用空格隔开。

输入文件中接下来的 $h$ 行描述初始时刻房间内的信息，每行包含 $w$ 个字符。这 $w\times h$ 个字符中每一个表示房间中的一个格子，意义如下：

1 至 9 ：表示该方格中有一个机器人，编号为这个数字；

x ：表示该方格有障碍物；

A ：表示该方格中有一个逆时针转向器；

C ：表示该方格中有一个顺时针转向器；

. 表示该方格为空地。

输出格式：

输出仅一个整数，表示最少需要推动的次数。若不能使所有机器人全部合并，输出 $-1$ 。

数据范围：

$1\le n \le 9, 1 \le w,h\le 500$

从合并方式可以看出，这很可能是一个区间dp。

考虑设 $f_{i,j,x,y}$ 表示 $i \sim j$ 号机器人合并到 $(x,y)$ 所需的最少次数。

考虑转移，首先是简单的合并（这里 $a\downarrow b + c$ 表示 $a \gets \min\{a,~b+c\}$ ）

$f_{i, j, x, y} \downarrow f_{i, k, x, y}+f_{k+1, j, x, y} \quad(i \leq k<j)$

然后是走路到的，设 $s(d,x,y)$ 表示 $(x,y)$ 往 $d$ 方向移动能到达的坐标，则

$f_{i,j,s(d,x,y)} \downarrow f_{i,j,x,y} + 1 \quad (d = 0,1,2,3)$

接着考虑转移顺序。第一部分只要简单的区间dp就可以了，第二部分就是斯坦纳树。

换句话说，由于我们可以由 $(x,y)$ 更新 $s(d,x,y)$ ，则我们可以把第二个式子看作三角不等式，即

$d_v \downarrow d_u + 1$

在外层枚举区间 $[i,j]$ 时，我们先转移合并的答案，然后跑一个 01bfs 就好了

时间复杂度 $\mathcal{O}(n^3wh)$

代码：（~~有些人懒得自己写，我不说是谁~~）

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N 10
#define M 525
#define L ((int)(4e6 + 15))
typedef int mat[M][M], (*pmat)[M];
typedef pair<int,int> pii;
#define Fi first
#define Se second
const int dx[4] = {0,-1,0,1}, dy[4] = {-1,0,1,0};

char mp[M][M]; mat hsh[4], f[N][N]; pmat ptr;
int n,W,H,ans=INF,hcnt,tcnt; pii ro[N], dest[4][M][M], que[L], fy[M * M]; 
bool cmp(pii x, pii y) { return ptr[x.Fi][x.Se] < ptr[y.Fi][y.Se]; }
int nxt(int x) { return (++x) == L ? 0 : x; }
int prv(int x) { return (x ? x : L) - 1; }
pii dfs(int x,int y,int d)
{
    pii &ret = dest[d][x][y]; if(ret.Se) return ret; if(hsh[d][x][y] == hcnt) return ret = pii(-1, -1); 
    hsh[d][x][y] = hcnt; int k = (unsigned)mp[x][y] - 64ull < 4ull ? (d - mp[x][y]) & 3 : d; 
    int tx = x + dx[k], ty = y + dy[k];
    return ret = (mp[tx][ty] == 'x' ? pii(x,y) : dfs(tx, ty, k));
}
void bfs(pmat dist, int tot)
{
    int h = 0, t = 0, i = 0, d; pii u,v;
    for(; i < tot || h != t; h = nxt(h))
    {
        u = que[h];
        if(h == t || (i < tot && dist[fy[i].Fi][fy[i].Se] < dist[u.Fi][u.Se]))
        { que[h = prv(h)] = u = fy[i++]; }
        for(d = 0; d < 4; d++)
        {
            v = dest[d][u.Fi][u.Se];
            if((~v.Fi) && dist[v.Fi][v.Se] > dist[u.Fi][u.Se] + 1)
            { dist[v.Fi][v.Se] = dist[u.Fi][u.Se] + 1; que[t] = v; t = nxt(t); }
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> W >> H; pmat f1, f2; int id;
    memset(mp, 'x', sizeof(mp)); memset(f, 0x3f, sizeof(f)); 
    for(int i = 1; i <= H; i++)
    {
        cin >> (mp[i] + 1); mp[i][W + 1] = 'x';
        for(int j = 1; j <= W; j++) if(isdigit(mp[i][j]))
        { id = mp[i][j] & 15; ro[id] = pii(i,j); f[id][id][i][j] = 0; }
    }
    for(int i = 1; i <= H; i++)
        for(int j = 1; j <= W; j++) if(mp[i][j] != 'x')
            for(int d = 0; d < 4; d++) { ++hcnt; dest[d][i][j] = dfs(i,j,d); }
    for(int i = 1; i <= n; i++) { fy[0] = ro[i], bfs(f[i][i], 1); }
    for(int d = 1; d < n; d++)
        for(int i = 1, j; i <= n - d; i++)
        {
            j = i + d; ptr = f[i][j];
            for(int k = i; k < j; k++)
            {
                f1 = f[i][k], f2 = f[k + 1][j];
                for(int r = 1; r <= H; r++)
                    for(int c = 1; c <= W; c++)
                        down(ptr[r][c], f1[r][c] + f2[r][c]);
            }
            tcnt = 0;
            for(int r = 1; r <= H; r++)
                for(int c = 1; c <= W; c++)
                    if(ptr[r][c] < INF) fy[tcnt++] = pii(r,c);
            sort(fy, fy + tcnt, cmp);  bfs(ptr, tcnt);
        }
    for(int r = 1; r <= H; r++)
        for(int c = 1; c <= W; c++) down(ans, f[1][n][r][c]);
    cout << (ans < INF ? ans : -1) << '\n';
    return 0;
}