题目：

分析：

卡了一天的神题……（OrzJumpmelon）

首先预处理出从点\(p\)向\(d\)方向出发最终能到达的点\(nxt[p][d]\)。这个可以直接记忆化搜索解决。如果出现环说明不能向这个方向出发，设为\(-1\)。

struct point{    int x, y;    point(const int _x = 0, const int _y = 0)        : x(_x), y(_y) {}};inline bool check(const point &p){    return p.x >= 0 && p.x < h && p.y >= 0 && p.y < w;}inline int ptoi(const point &p){    return p.x * w + p.y;}bool vis[P][DIR], insta[P][DIR];int dfs(const point &u, const int &d){    int id = ptoi(u);    if (vis[id][d])        return nxt[id][d];    if (insta[id][d])    {        vis[id][d] = true;        return nxt[id][d] = -1;    }    int dd = d;    if (map[id] == LEFT)        dd = (dd + 1) & 3;    if (map[id] == RIGHT)        dd = (dd + 3) & 3;    point v = point(u.x + dx[dd], u.y + dy[dd]);    if (!check(v) || map[ptoi(v)] == WALL)    {        vis[id][d] = true;        return nxt[id][d] = id;    }    else    {        insta[id][d] = true;        nxt[id][d] = dfs(v, dd);        insta[id][d] = false;        vis[id][d] = true;        return nxt[id][d];    }}

然后考虑用\(dp[i][j][u]\)表示令编号为\([i,j]\)的复合机器人在\(u\)点的最少步数，最终答案就是\(min(dp[0][n-1][u])\)。有两种转移方式：

1.把\([i,k]\)和\((k,j]\)两个机器人在\(p\)点拼起来，即：

\[dp[i][j][u]=min(dp[i][k][u]+dp[k+1][j][u])\]

2.把\([i,j]\)机器人推到\(u\)点，即（其中\(v\)能一步走到\(u\)即存在满足\(nxt[v][d]=u\)的\(d\)）：

\[dp[i][j][u]=dp[i][j][v]+1\]

第一种直接区间DP即可。第二种存在循环更新，但是长得很像最短路……

于是我码了Dijkstra，卡常卡到死也没卡过去，还借此机会跟Jumpmelon谝了一天qwq。

下面介绍一下Jumpmelon给我讲的优化：开两个队列，第一个队列是一开始的点，按照\(dis\)排好序（\(dis[u]\)表示\(dp[i][j][u]\)，下同）；第二个队列是已经更新，等待用来更新别的点的队列，初始为空。每次将两个队列队首中\(dis\)较小的一个取出来（相当于Dijkstra的堆顶）来松弛其他点，这样复杂度是\(O(n+m)\)的，成功去掉堆的\(\log m\)。为什么这样是对的呢？

注意到所有边权都是\(1\)，于是点\(v\)被更新时第二个队列的队尾（如果存在）的\(dis\)一定不会大于\(dis[v]\)，所以直接把\(v\)插到队尾不会影响第二个队列的有序性。原因如下。

考虑反证。假设之前第二个队列是有序的，在某一次更新后变得无序了。设用于更新的点是\(u\)，被更新的点是\(v\)，更新前第二个队列的队尾为\(t\)，满足\(dis[v]=dis[u]+1\)，\(dis[t]>dis[v]\)。由于边权都是\(1\)，那么曾用于更新\(t\)的点\(p\)满足\(dis[p]=dis[t]-1\geq dis[v]>dis[u]\)。既然\(dis[u]<dis[p]\)，由于之前两个队列都是有序的，且每次是取出两队列队首的较小值更新，那么\(u\)显然应该在\(p\)之前被取出，矛盾。所以这种情况不存在。既然能保持两个队列的有序性，那么就保证了每次取出\(dis\)最小的点，也就不需要堆了。（没上文化课，表达能力为\(0\)，自己都觉得佶屈聱牙跟个T嘴z子z一样。感性理解就好）。

代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #undef i#undef j#undef k#undef true#undef false#undef min#undef max#undef sort#undef swap#undef if#undef while#undef for#undef printf#undef scanf#undef putchar#undef getchar#define _ 0using namespace std;namespace zyt{ template
           
             inline bool read(T &x) { char c; bool f = false; x = 0; do c = getchar(); while (c != EOF && c != '-' && !isdigit(c)); if (c == EOF) return false; if (c == '-') f = true, c = getchar(); do x = x * 10 + c - '0', c = getchar(); while (isdigit(c)); if (f) x = -x; return true; } inline bool read(char &c) { do c = getchar(); while (c != EOF && !isgraph(c)); return c != EOF; } template
            
              inline void write(T x) { static char buf[20]; char *pos = buf; if (x < 0) putchar('-'), x = -x; do *pos++ = x % 10 + '0'; while (x /= 10); while (pos > buf) putchar(*--pos); } const int W = 5e2, P = W * W, N = 9, DIR = 4, INF = 0x3f3f3f3f, B = 18; const int U = 0, L = 1, D = 2, R = 3, WALL = N, LEFT = N + 1, RIGHT = N + 2, BLANK = N + 3; const int dx[DIR] = {-1, 0, 1, 0}; const int dy[DIR] = {0, -1, 0, 1}; int n, w, h, p, nxt[P][DIR], map[P], dp[N][N][P]; struct point { int x, y; point(const int _x = 0, const int _y = 0) : x(_x), y(_y) {} }; inline bool check(const point &p) { return p.x >= 0 && p.x < h && p.y >= 0 && p.y < w; } inline int ptoi(const point &p) { return p.x * w + p.y; } bool vis[P][DIR], insta[P][DIR]; int dfs(const point &u, const int &d) { int id = ptoi(u); if (vis[id][d]) return nxt[id][d]; if (insta[id][d]) { vis[id][d] = true; return nxt[id][d] = -1; } int dd = d; if (map[id] == LEFT) dd = (dd + 1) & 3; if (map[id] == RIGHT) dd = (dd + 3) & 3; point v = point(u.x + dx[dd], u.y + dy[dd]); if (!check(v) || map[ptoi(v)] == WALL) { vis[id][d] = true; return nxt[id][d] = id; } else { insta[id][d] = true; nxt[id][d] = dfs(v, dd); insta[id][d] = false; vis[id][d] = true; return nxt[id][d]; } } void Shortest_Path(const int l, const int r) { typedef pair
             
               pii; static pii tmp[P]; static bool vis[P]; static queue
              
                q1, q2; while (!q1.empty()) q1.pop(); while (!q2.empty()) q2.pop(); memset(vis, 0, sizeof(bool[p])); int *dis = dp[l][r], cnt = 0; for (int i = 0; i < p; i++) if (map[i] != WALL && dis[i] < INF) tmp[cnt++] = make_pair(dis[i], i), vis[i] = true; sort(tmp, tmp + cnt); for (int i = 0; i < cnt; i++) q1.push(tmp[i].second); while (!q1.empty() || !q2.empty()) { int u = ((q1.empty() || (!q2.empty() && dis[q1.front()] > dis[q2.front()])) ? q2.front() : q1.front()); if (!q1.empty() && u == q1.front()) q1.pop(); else q2.pop(); vis[u] = false; for (int i = 0; i < DIR; i++) { int v = nxt[u][i]; if (~v && dis[v] > dis[u] + 1) { dis[v] = dis[u] + 1; if (!vis[v]) q2.push(v), vis[v] = true; } } } } int work() { read(n), read(w), read(h); p = w * h; for (int i = 0; i < n; i++) for (int j = i; j < n; j++) memset(dp[i][j], INF, sizeof(int[p])); for (int i = 0; i < p; i++) { char c; read(c); if (isdigit(c)) { map[i] = c - '1'; dp[map[i]][map[i]][i] = 0; } else if (c == '.') map[i] = BLANK; else if (c == 'x') map[i] = WALL; else if (c == 'A') map[i] = LEFT; else map[i] = RIGHT; } for (int i = 0; i < h; i++) for (int j = 0; j < w; j++) { int id = ptoi(point(i, j)); if (map[id] != WALL) for (int d = 0; d < DIR; d++) nxt[id][d] = dfs(point(i, j), d); } for (int l = 1; l <= n; l++) for (int i = 0; i + l - 1 < n; i++) { int j = i + l - 1; for (int u = 0; u < p; u++) if (map[u] != WALL) for (int k = i; k < j; k++) dp[i][j][u] = min(dp[i][j][u], dp[i][k][u] + dp[k + 1][j][u]); Shortest_Path(i, j); } int ans = INF; for (int i = 0; i < p; i++) ans = min(ans, dp[0][n - 1][i]); if (ans == INF) write(-1); else write(ans); return (0^_^0); }}int main(){ return zyt::work();}