h*w的网格图, 障碍不可通行, 逆/顺时针转向器强制通过者转向, n个机器人. 多个机器人可占同一个格子, 并且不会挡路. 机器人不能自发移动或停止, 可以横向或纵向推它一把, 它会沿直线移动直到碰到边界或障碍物. 机器人的编号是一个区间[l,r], [l,m]和[m+1,r]可以合并成机器人[l,r]; 初始编号[i,i] (1≤i≤n). 静止时, 机器人会自动合并. 给出网格图 (空地, 障碍, 转向器, 机器人), 问最少推多少次, 机器人可合并成[1,n], 或报告无解. (n≤9, w,h≤500) 首先, 把图刨出来.
搜索的话状态集太大, 尝试DP: dp[l][r][i][j]表示编号[l,r]的机器人在(i,j)处合并的最小代价. 但是, 转移除了在图上暴力跑一遍, 没想到什么好方法.
查题解, "很裸的斯坦纳树"?? 这是什么鬼......后来发觉, 它意思是, 本问题的转移方程和方式和最小斯坦纳树问题很相像; 并不是要用斯坦纳树解决本问题.
修改一下状态: dp[l][r][i][j]表示编号[l,r]的机器人合并后走到(i,j)处的最小代价, 那么
dp[l][r][i][j] = min {
min { dp[l][m][i][j] + dp[m+1][r][i][j] | l <= m < r } (1),
min { dp[l][r][i'][j'] + 1 | (i',j')->(i,j) in E } (2)
}(1)好处理. (2)是正确的, 但无法直接用来递推, 因为缺乏明确的转移顺序 - 图不保证无环. 但我们知道, 最优解是客观存在的 (收敛), 并且满足三角不等式. 所以跑一发SPFA即可 (如: NOIP 2009 最优贸易).
据说玄学复杂度的SPFA不能通过本题. 注意到这个形式本身就符合多源最短路 (不像最优贸易, 运算是取max), 边权又都是1, 所以改跑BFS.
添加超级源和一些中间结点, 就变成边权均为1的单源最短路. 无需真的建出它们, 把所有源点按初始值从小到大排序, 模拟这个过程即可 - BFS找最短路的正确性保证: 队列中的距离始终非严格单增.
不能用if (!vis[v])来判断是否应该更新v, 因为v可能是一个源点. 用if (d[v] > d[u] + 1).
enum Dir {
UP, RIGHT, DOWN, LEFT
};
struct Point {
int x, y;
Point(int x=-1, int y=-1): x(x), y(y) {}
bool operator==(const Point& o) const
{
return x == o.x && y == o.y;
}
};
const Point nil;
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1}, inf = (1<<30)-1, N = 9, W = 502;
int n, w, h;
char M[W][W];
Point to[W][W][4], pos[N];
Point dfs(int x, int y, int d)
{
static short vis[W][W][4];
short& v = vis[x][y][d];
Point& t = to[x][y][d];
if (v == -1) return nil;
if (v == 1) return t;
v = -1;
char c = M[x][y];
if (c == 'A' || c == 'C')
d = (d + (c == 'A' ? 3 : 1)) % 4;
if (c != 'x') {
if (M[x+dx[d]][y+dy[d]] == 'x')
t = Point(x, y);
else
t = dfs(x + dx[d], y + dy[d], d);
}
v = 1;
return t;
}
void build()
{
rep (i, 1, h+1) {
rep (j, 1, w+1) {
rep (k, 0, 4)
dfs(i, j, k);
if (isdigit(M[i][j]))
pos[M[i][j]-'1'] = Point(i, j);
}
}
}
int (*ptr)[W];
bool cmp(const Point& p, const Point& q)
{
return ptr[p.x][p.y] < ptr[q.x][q.y];
}
void bfs(Point s[], int m, int d[W][W])
{
static short vis[W][W], now;
++now;
ptr = d;
sort(s, s+m, cmp);
int p = 0;
queue<Point> Q;
while (!Q.empty() || p < m) {
Point u, x;
if (Q.empty() || (x = Q.front(), d[s[p].x][s[p].y] == d[x.x][x.y])) {
u = s[p++];
vis[u.x][u.y] = now;
} else {
u = Q.front();
Q.pop();
}
int du = d[u.x][u.y];
rep (i, 0, 4) {
Point v = to[u.x][u.y][i];
if (v == nil) continue;
int& dv = d[v.x][v.y];
if (dv > du + 1) {
dv = du + 1;
vis[v.x][v.y] = now;
Q.push(v);
}
}
while (p < m && vis[s[p].x][s[p].y] == now) ++p;
}
}
int solve()
{
static int dp[N][N][W][W];
static Point s[W*W];
int top = 0;
fill_n(***dp, sizeof(dp)/sizeof(int), inf);
rep (i, 0, n) {
Point& p = pos[i];
dp[i][i][p.x][p.y] = 0;
s[0] = p;
bfs(s, 1, dp[i][i]);
}
per (l, n-2, 0) {
rep (r, l+1, n) {
top = 0;
rep (m, l, r) rep (i, 1, h+1) rep (j, 1, w+1)
dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][m][i][j] + dp[m+1][r][i][j]);
rep (i, 1, h+1) rep (j, 1, w+1)
if (dp[l][r][i][j] < inf)
s[top++] = Point(i, j);
bfs(s, top, dp[l][r]);
}
}
int ans = inf;
rep (i, 1, h+1) rep (j, 1, w+1) ans = min(ans, dp[0][n-1][i][j]);
return ans == inf ? -1 : ans;
}
int main()
{
scanf("%d%d%d", &n, &w, &h);
rep (i, 1, w+1)
M[0][i] = M[h+1][i] = 'x';
rep (i, 1, h+1) {
scanf("%s", M[i]+1);
M[i][0] = M[i][w+1] = 'x';
}
build();
printf("%d\n", solve());
return 0;
}