题目链接 题目描述 VRI（Voltron 机器人学会）的工程师建造了 n n n 个机器人。任意两个兼容的机 器人站在同一个格子时可以合并为一个复合机器人。
我们把机器人用 1 1 1 至 n n n 编号（ n ≤ 9 n ≤ 9 n≤9）。如果两个机器人的编号是连续的，那 么它们是兼容的，可以合并成一个复合机器人。最初这 n n n 个机器人各自都只有唯 一的编号。而一个由两个或以上的机器人合并构成的复合机器人拥有两个编号， 分别是构成它的所有机器人中最小和最大的编号。
例如， 2 2 2 号机器人只可以与 1 1 1 号或 3 3 3 号机器人合并。若 2 2 2 号机器人与 3 3 3 号机 器人合并，可构成编号为 2 − 3 2-3 2−3 的复合机器人。如果编号为 2 − 3 2-3 2−3 的复合机器人与编 号为 4 − 6 4-6 4−6 的复合机器人合并，可构成编号为 2 − 6 2-6 2−6 的复合机器人。当所有机器人合 并以后则构成 1-n 复合机器人。
工程师把这 n n n 个机器人放在了一个封闭的房间中，房间四周均是墙。该房间 被划分成 w × h w × h w×h 个方格。有些方格有障碍物，机器人不可经过或停留；其余方格 允许多个机器人停留，同时允许机器人经过。任何时候一个机器人只占用一个方 格。初始时刻，所有机器人均在不同的方格中。
这些原始的机器人不会自发地移动。它们只有被工程师沿 x 轴或 y 轴推动 后，才会沿推动的方向不断向前直线移动，直至碰到障碍物或墙停止移动。停止 移动后，它会扫描当前的格子是否存在可以与它合并的机器人，如果有，则合并 并继续检查，直至不能再合并为止。工程师只能沿水平向左、水平向右、竖直向 上、竖直向下四个方向推动机器人，并且，在机器人尚未停止移动时，不允许推 动其它机器人，因此任何时刻，房间中都只能有一个机器人移动。
为了帮助机器人转向，工程师在一些格子中放置了转向器。具体地说，转向 器分为顺时针转向器（右转器）和逆时针转向器（左转器），顺时针转向器可以 使到达该格子的机器人沿顺时针方向转向 90 ° 90° 90°；逆时针转向器可以使到达该格 子的机器人沿逆时针方向转向 90 ° 90° 90°。
现在，我们将告诉你初始时刻房间内的信息。请你计算工程师最少共计需要 推动机器人多少次，才能把所有的 n n n 个机器人全部合并（如果可能的话）。
输入格式 你的程序必须从标准输入读入。
输入的第 1 1 1 行包含 3 3 3 个整数 n n n、 w w w 和 h h h，用 空格隔开。
输入文件中接下来的 h h h 行描述初始时刻房间内的信息，每行包含 w w w 个字符。 这 w × h w × h w×h 个字符中每一个表示房间中的一个格子，意义如下：
‘1’至‘9’：表示该方格中有一个机器人，编号为这个数字；
‘x’：表示该方格有障碍物；
‘A’：表示该方格中有一个逆时针转向器；
‘C’：表示该方格中有一个顺时针转向器；
‘.’：表示该方格为空地。
输出格式 你的程序必须输出到标准输出。输出仅一个整数，表示最少需要推动的次数。 若不能使所有机器人全部合并，输出 − 1 -1 −1。
输入输出样例 输入 #1
4 10 5 1......... AA...x4... ..A..x.... 2....x.... ..C.3.A...输出 #1
5说明/提示 测例满足 n ≤ 9 n ≤ 9 n≤9， w ≤ 500 w ≤ 500 w≤500 且 h ≤ 500 h ≤ 500 h≤500 关键点相邻的数字可以合并，合并后拥有合并前两个节点的数字，求合并次数。
首先预处理出图中任意一没有非障碍物的格子如果向某个方向移动最终会停留在那个格子上。之后操作类似与求解斯坦纳树，只不过状态由任意点集变为连续的点集，因此dp时由枚举子集变为区间dp。
具体操作为：设 d s t [ x ] [ y ] [ z ] dst[x][y][z] dst[x][y][z] 表示从点 ( x , y ) (x,y) (x,y) 沿 z z z 方向出发最终会停留的格子，利用记忆化搜索预处理对于可能路径连成环导致停不下来的情况用 v i s vis vis 数组标记来判断。
接下来设 d p [ l ] [ r ] [ x ] [ y ] dp[l][r][x][y] dp[l][r][x][y] 表示将编号 x ∼ y x\sim y x∼y 的点合并在一起所需的最少操作数。
转移方程为： d p [ l ] [ r ] [ x ] [ y ] = { min l ≤ t < r ( d p [ l ] [ r ] [ x ] [ y ] , d p [ l ] [ t ] [ x ] [ y ] + d p [ t + 1 ] [ r ] [ x ] [ y ] ) min d s t [ u ] [ v ] [ z ] = ( x , y ) ( d p [ l ] [ r ] [ x ] [ y ] , d p [ l ] [ r ] [ u ] [ v ] + 1 ) dp[l][r][x][y]=\left\{\begin{matrix} \min\limits_{l\le t<r}(dp[l][r][x][y],dp[l][t][x][y]+dp[t+1][r][x][y])\\ \min\limits_{dst[u][v][z]=(x,y)}(dp[l][r][x][y],dp[l][r][u][v]+1) \end{matrix}\right. dp[l][r][x][y]=⎩⎨⎧l≤t<rmin(dp[l][r][x][y],dp[l][t][x][y]+dp[t+1][r][x][y])dst[u][v][z]=(x,y)min(dp[l][r][x][y],dp[l][r][u][v]+1) 如果第二个方程用spfa转移，则时间复杂度为 O ( 4 w h + n 3 w h k n ) O(4wh+n^3whkn) O(4wh+n3whkn) 。
题目卡常，spfa需要松弛操作且初始状态需要排序再开O2才能过。(用Dijkstra开O2也能过，但是更慢)
用set优化枚举范围可能会被毒瘤数据卡得多一个log并且可能超空间。
#include<bits/stdc++.h> #define pii pair<int,int> #define fi first #define se second #define INF 0x3f3f3f3f using namespace std; inline int qr() { int f = 0, fu = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-')fu = -1; c = getchar(); } while (c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + c - 48; c = getchar(); } return f * fu; } const int N = 505; const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, 1, 0, -1}; char a[N][N]; int n, m, k; pii dst[N][N][4], p[N * N]; bool vis[N][N][4], v[N][N]; int dp[10][10][N][N], tot; pii dfs(int x, int y, int z) { if (dst[x][y][z].fi)return dst[x][y][z]; if (vis[x][y][z])return dst[x][y][z] = {-1, -1}; vis[x][y][z] = true; int nx = x + dx[z], ny = y + dy[z]; if (a[nx][ny] == 'x')dst[x][y][z] = {x, y}; else if (a[nx][ny] == 'A')dst[x][y][z] = dfs(nx, ny, (z + 3) % 4); else if (a[nx][ny] == 'C')dst[x][y][z] = dfs(nx, ny, (z + 1) % 4); else dst[x][y][z] = dfs(nx, ny, z); vis[x][y][z] = false; return dst[x][y][z]; } deque<pii > q; inline void spfa(int l, int r) { while (!q.empty()) { pii t = q.front(); q.pop_front(), v[t.fi][t.se] = false; for (register int i = 0; i < 4; i++) { pii nxt = dst[t.fi][t.se][i]; if (!~nxt.fi)continue; if (dp[l][r][nxt.fi][nxt.se] > dp[l][r][t.fi][t.se] + 1) { dp[l][r][nxt.fi][nxt.se] = dp[l][r][t.fi][t.se] + 1; if (!v[nxt.fi][nxt.se]) { v[nxt.fi][nxt.se] = true; q.empty() || dp[l][r][nxt.fi][nxt.se] > dp[l][r][q.front().fi][q.front().se] ? q.emplace_back(nxt) : q.emplace_front(nxt); } } } } } int main() { k = qr(), m = qr(), n = qr(); for (register int i = 1; i <= n; i++)scanf("%s", a[i] + 1); for (register int i = 0; i <= n + 1; i++)a[i][0] = a[i][m + 1] = 'x'; for (register int i = 0; i <= m + 1; i++)a[0][i] = a[n + 1][i] = 'x'; for (register int x = 1; x <= n; x++) for (register int y = 1; y <= m; y++) if (a[x][y] != 'x')for (int z = 0; z < 4; z++)dfs(x, y, z); memset(dp, 0x3f, sizeof(dp)); for (register int i = 1; i <= n; i++) for (register int j = 1; j <= m; j++) { if (a[i][j] != 'x')p[++tot] = {i, j}; if (a[i][j] >= '1' && a[i][j] <= '9') { int x = a[i][j] - '0'; dp[x][x][i][j] = 0; } } for (register int len = 1; len <= k; len++) for (register int l = 1; l <= k - len + 1; l++) { int r = l + len - 1; for (register int t = l; t <= r - 1; t++) for (int i = 1; i <= tot; i++) dp[l][r][p[i].fi][p[i].se] = min(dp[l][r][p[i].fi][p[i].se], dp[l][t][p[i].fi][p[i].se] + dp[t + 1][r][p[i].fi][p[i].se]); for (register int i = 1; i <= tot; i++) if (dp[l][r][p[i].fi][p[i].se] != INF) { v[p[i].fi][p[i].se] = true; q.empty() || dp[l][r][p[i].fi][p[i].se] > dp[l][r][q.front().fi][q.front().se] ? q.emplace_back(p[i].fi, p[i].se) : q.emplace_front(p[i].fi, p[i].se); } sort(q.begin(), q.end(), [&](pii i, pii j) { return dp[l][r][i.fi][i.se] < dp[l][r][j.fi][j.se]; }); spfa(l, r); } int ans = INF; for (register int i = 1; i <= tot; i++)ans = min(ans, dp[1][k][p[i].fi][p[i].se]); printf("%d\n", ans == INF ? -1 : ans); return 0; }