题目
题目链接：https://www.luogu.com.cn/problem/P3638
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 个机器人全部合并（如果可能的话）。
n ≤ 9，w ≤ 500，h ≤ 500。
思路
先预处理出每一个位置从任意方向出发会到达哪个点。这部分可以记忆化搜索。
设 (f[i][j][k]) 表示区间 ([i,j]) 的机器人全部到点 (k) 的最少操作次数。那么有两种转移：
- 当 (k) 相同的时候，内部进行转移
- 当 (k) 不同的时候，外部进行转移
其中 (mathrm{nxt}_{k,l}) 表示从 (k) 出发，方向为 (l) 最终会到达的位置。
虽然第二个转移是有环的，且满足三角形不等式。但是我们发现其实这两个转移显然就是斯坦纳树的转移。所以我们可以用 SPFA 来进行转移。
直接跑 SPFA 是过不了的。这道题需要一定的卡常。我们发现边权均为 (1)，所以直接用两个队列储存初始位置的状态和转移到的位置的状态，每次取两个队头的较小值来转移即可。其实这就是一个 BFS。具体可以见代码。
时间复杂度 (O(nmk^3))。
代码
由于这道题相对卡常，所以代码可能十分不美观。
数组建议把范围小那一维的放在前面，因为这样可以让更多的内存连续，加快速度。
#include <bits/stdc++.h>
using namespace std;
const int N=505,M=11,Inf=1e9;
const int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int n,r,c,lim,ans,q1[N*N*8],q2[N*N*8],nxt[4][N*N],f[M][M][N*N],cnt[N*N*36];
bool vis[4][N][N];
char a[N][N];
inline int ID(int x,int y)
{
return (x-1)*c+y;
}
int dfs(int x,int y,int k)
{
if (vis[k][x][y]) return nxt[k][ID(x,y)]=-1;
if (nxt[k][ID(x,y)]) return nxt[k][ID(x,y)];
vis[k][x][y]=1;
if (a[x][y]=='.' || isdigit(a[x][y]))
{
if (a[x+dx[k]][y+dy[k]]!='x')
nxt[k][ID(x,y)]=dfs(x+dx[k],y+dy[k],k);
else nxt[k][ID(x,y)]=ID(x,y);
}
if (a[x][y]=='A')
{
int k1=(k+3)%4;
if (a[x+dx[k1]][y+dy[k1]]!='x')
nxt[k][ID(x,y)]=dfs(x+dx[k1],y+dy[k1],k1);
else nxt[k][ID(x,y)]=ID(x,y);
}
if (a[x][y]=='C')
{
int k1=(k+1)%4;
if (a[x+dx[k1]][y+dy[k1]]!='x')
nxt[k][ID(x,y)]=dfs(x+dx[k1],y+dy[k1],k1);
else nxt[k][ID(x,y)]=ID(x,y);
}
vis[k][x][y]=0;
return nxt[k][ID(x,y)];
}
inline void bfs(int L,int R)
{
for (int i=0;i<=lim;i++) cnt[i]=0;
lim=0;
for (int k=1;k<=r*c;k++)
if (f[L][R][k]<Inf) cnt[f[L][R][k]]++,lim=max(lim,f[L][R][k]);
for (int i=1;i<=lim;i++) cnt[i]+=cnt[i-1];
int h1=1,h2=1,t1=cnt[lim],t2=0;
for (int k=1;k<=r*c;k++)
if (f[L][R][k]<Inf) q1[cnt[f[L][R][k]]--]=k;
while (h1<=t1 || h2<=t2)
{
int u=(h2>t2 || f[L][R][h1]<f[L][R][h2])?q1[h1++]:q2[h2++];
for (int i=0;i<=3;i++)
if (nxt[i][u]!=-1 && f[L][R][nxt[i][u]]>f[L][R][u]+1)
{
f[L][R][nxt[i][u]]=f[L][R][u]+1;
q2[++t2]=nxt[i][u];
}
}
}
void solve()
{
for (int i=n;i>=1;i--)
for (int j=i;j<=n;j++)
{
for (int k=1;k<=r*c;k++)
for (int l=i;l<j;l++)
f[i][j][k]=min(f[i][j][k],f[i][l][k]+f[l+1][j][k]);
bfs(i,j);
}
}
int main()
{
scanf("%d%d%d",&n,&c,&r);
for (int i=1;i<=r;i++)
scanf("%s",a[i]+1);
for (int i=0;i<=c+1;i++) a[0][i]=a[r+1][i]='x';
for (int i=0;i<=r+1;i++) a[i][0]=a[i][c+1]='x';
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
for (int k=0;k<=3;k++)
if (a[i][j]!='x') nxt[k][ID(i,j)]=dfs(i,j,k);
memset(f,0x3f3f3f3f,sizeof(f));
for (int i=1;i<=r;i++)
for (int j=1;j<=c;j++)
if (isdigit(a[i][j]))
f[a[i][j]-48][a[i][j]-48][ID(i,j)]=0;
solve();
ans=Inf;
for (int i=1;i<=r*c;i++)
ans=min(ans,f[1][n][i]);
if (ans<Inf) printf("%d",ans);
else printf("-1");
return 0;
}