P3638 [APIO2013] 机器人

</details>
#include <stdio.h>
#include <string.h>
#include <algorithm>
typedef signed char byte;
const int inf = 0x3f3f3f3f;
const int N = 502, M = 10, V = N * N, E = N * N * 4;
const byte dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int c, n, m;
char map[N][N];
int id[N][N], idt; // 对应的编号(映射)
int f[M][M][N * N]; // 合并出编号为[l..r]的机器人(在i号位置)的最少步数
int ed[N][N][4]; // 从(x,y,d)开始最后走到的点的编号,如果为0表示没有遍历过,如果为-1表示在环上
byte in_stk[N][N]; // 是否在栈中
int h[V], e[E], nxt[E], idx;
void add(int a, int b) { e[++ idx] = b, nxt[idx] = h[a], h[a] = idx; }
int dfs(int x, int y, byte d) { // 求出ed
	if(in_stk[x][y] >> d & 1) return ed[x][y][d] = -1;
	if(ed[x][y][d]) return ed[x][y][d];
	in_stk[x][y] |= 1 << d;
	int hx = x + dx[d], hy = y + dy[d];
	if(map[hx][hy] == 'x' || !map[hx][hy]) ed[x][y][d] = id[x][y];
	else if(map[hx][hy] == 'A') ed[x][y][d] = dfs(hx, hy, (d + 3) & 3);
	else if(map[hx][hy] == 'C') ed[x][y][d] = dfs(hx, hy, (d + 1) & 3);
	else ed[x][y][d] = dfs(hx, hy, d);
	in_stk[x][y] ^= 1 << d;
	return ed[x][y][d];
}
int q1[V], q2[E * 4];
int sum[N * N]; // 计数排序
bool st[N * N];
void solve(int *dist) { // 求最短路来转移
	int h1 = 0, t1 = 0, h2 = 0, t2 = 0;
	int maxx = 0; // 先排序
	for(int i = 1; i <= idt; i ++) if(dist[i] < inf) ++ sum[dist[i]], maxx = std::max(maxx, dist[i]);
	for(int i = 1; i <= maxx; i ++) sum[i] += sum[i - 1];
	for(int i = 1; i <= idt; i ++) if(dist[i] < inf) q1[-- sum[dist[i]]] = i, ++ t1, st[i] = true;
	for(int i = 1; i <= maxx; i ++) sum[i] = 0;
	memset(st + 1, 0, idt);
	while(h1 != t1 || h2 != t2) {
		int u = (h1 == t1 ? inf : q1[h1]) < (h2 == t2 ? inf : q2[h2]) ? q1[h1 ++] : q2[h2 ++], d = dist[u] + 1;
		st[u] = false;
		for(int i = h[u], v; i; i = nxt[i])
			dist[v=e[i]] > d && (dist[v] = d, !st[v] && (st[v] = true, q2[t2 ++] = v));
	}
}
int main() {
	scanf("%d%d%d", &c, &m, &n);
	for(int i = 1; i <= n; i ++) {
		scanf("%s", map[i] + 1);
		for(int j = 1; j <= m; j ++) if(map[i][j] != 'x') id[i][j] = ++ idt;
	}
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++) if(map[i][j] != 'x')
			for(int k = 0; k < 4; k ++)
				if(dfs(i, j, k) != -1 && dfs(i, j, k) != id[i][j])
					add(id[i][j], dfs(i, j, k)); // 从(i,j)出发可到达的点
	for(int i = 1; i <= c; i ++)
		for(int j = 1; j <= c; j ++) memset(f[i][j] + 1, 0x3f, idt << 2);
	for(int i = 1; i <= n; i ++)
		for(int j = 1; j <= m; j ++) if('0' < map[i][j] && map[i][j] <= '9')
			f[map[i][j] - '0'][map[i][j] - '0'][id[i][j]] = 0;
	for(int l = c; l; l --) for(int r = l; r <= c; r ++) {
		for(int k = l; k < r; k ++) for(int i = 1; i <= idt; i ++)
			f[l][r][i] = std::min(f[l][r][i], f[l][k][i] + f[k+1][r][i]); // 合并机器人
		solve(f[l][r]); // 计算最短路(处理机器人被推动的转移)
	}
	int res = inf;
	for(int i = 1; i <= idt; i ++) res = std::min(res, f[1][c][i]);
	printf("%d\n", res >= 0x3f3f3f3f ? -1 : res);
	return 0;
}