标签：必须 第一步 mes 解决 radius mem 方向 amp 逆时针
题目描述
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 个机器人全部合并（如果可能的话）。
输入输出格式
输入格式：
你的程序必须从标准输入读入。
输入的第 1 行包含 3 个整数 n、w 和 h，用 空格隔开。
输入文件中接下来的 h 行描述初始时刻房间内的信息，每行包含 w 个字符。 这 w × h 个字符中每一个表示房间中的一个格子，意义如下：
‘1’至‘9’：表示该方格中有一个机器人，编号为这个数字；
‘x’：表示该方格有障碍物；
‘A’：表示该方格中有一个逆时针转向器；
‘C’：表示该方格中有一个顺时针转向器；
‘.’：表示该方格为空地。
输出格式：
你的程序必须输出到标准输出。输出仅一个整数，表示最少需要推动的次数。 若不能使所有机器人全部合并，输出-1。
输入输出样例
输入样例#1： 复制
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
说明
第一步：向右推动 3 号机器人，当它碰到转向器后会向上继续移动，直至碰 到墙壁停止移动。
第二步：向上推动 4 号机器人，当它碰到墙壁后停止移动，与 3 号机器人合 并，构成 3-4 号机器人
第三步：向上推动 2 号机器人，当它碰到转向器后会向左移动，由于左侧为 墙壁，故停留在原地。
第四步：向右推动 2 号机器人，由于它在一个转向器上，故它会向上移动， 直至碰到墙壁停止移动，与 1 号机器人合并，构成 1-2 号机器人。
第五步：向左推动 3-4 号机器人，当它碰到墙壁后停止移动，与 1-2 号机器 人合并，构成 1-4 号机器人。
我们将使用以下 4 类输入测例测试你的程序
测例满足 n ≤ 9，w ≤ 500 且 h ≤ 500。
因为每一次只能与相邻机器人合并
所以f[l][r][x][y]表示编号l~r的机器人在(x,y)合并的最小代价
预处理出d[i][x][y]表示i方向能走到哪个点
然后又两种转移：
f[l][r][x][y]=min(f[l][k][x][y]+f[k+1][r][x][y])
f[l][r][dx][dy]=min(f[l][r][x][y]+1)
第二种可以用SPFA解决
但是会超时，用单调队列也解决不了
用双端队列，第一个储存所有起始点，按f[l][r][x][y]排序
另一个队列储存到的点
每一次从两个队列中选出最小的f[l][r][x][y]进行拓展
不要用STL
1 #include 2 #include 3 #include
4 #include 5 #include 6 #include 7 using namespace std;
8 struct ZYYS
9 {
10 int x,y,d;
11 }a[501],q[505001],Q[505001];
12 char s[601][601];
13 const int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
14 int f[10][10][501][501],inf=1e9,n,m,cnt,g[5][501][501],tag[5][501][501],top,vis[501][501],ans;
15 bool cmp(ZYYS a,ZYYS b)
16 {
17 return a.db.d;
18 }
19 int cal(int x,int y)
20 {
21 return (x-1)*m+y;
22 }
23 int dfs(int k,int x,int y)
24 {
25 if (x0||x>n||y0||y>m) return 0;
26 if (g[k][x][y]) return g[k][x][y];
27 if (s[x][y]==‘x‘) return 0;
28 if (tag[k][x][y]) return -1;
29 tag[k][x][y]=1;
30 int t=k;
31 if (s[x][y]==‘A‘) k=(k+1)%4;
32 if (s[x][y]==‘C‘) k=(k+3)%4;
33 g[t][x][y]=dfs(k,x+dx[k],y+dy[k]);
34 tag[t][x][y]=0;
35 if (g[t][x][y]==0) g[t][x][y]=cal(x,y);
36 return g[t][x][y];
37 }
38 int main()
39 {int i,j,k,l,r,L,R,LL,RR;
40 cin>>cnt>>m>>n;
41 for (i=1;i)
42 for (j=1;j)
43 for (l=1;l)
44 for (k=1;k)
45 f[l][k][i][j]=inf;
46 for (i=1;i)
47 {
48 scanf("%s",s[i]+1);
49 for (j=1;j)
50 {
51 if (s[i][j]>=‘1‘&&s[i][j]‘9‘)
52 k=s[i][j]-‘0‘,a[k].x=i,a[k].y=j,f[k][k][i][j]=0;
53 }
54 }
55 for (i=1;i)
56 {
57 for (j=1;j)
58 if (s[i][j]!=‘x‘)
59 {
60 for (k=0;k4;k++)
61 g[k][i][j]=dfs(k,i,j);
62 }
63 }
64 for (l=cnt;l>=1;l--)
65 for (r=l;r)
66 {
67 for (k=l;k)
68 for (i=1;i)
69 for (j=1;j)
70 f[l][r][i][j]=min(f[l][r][i][j],f[l][k][i][j]+f[k+1][r][i][j]);
71 top=0;
72 memset(vis,0,sizeof(vis));
73 for (i=1;i)
74 {
75 for (j=1;j)
76 {
77 if (f[l][r][i][j]!=inf) q[++top]=(ZYYS){i,j,f[l][r][i][j]},vis[i][j]=1;
78 }
79 }
80 sort(q+1,q+top+1,cmp);
81 L=0;R=top;LL=0;RR=0;
82 while (L!=R||LL!=RR)
83 {//cout
84 ZYYS u;
85 if (L==R||(LL!=RR&&f[l][r][q[L].x][q[L].y]>f[l][r][Q[LL].x][Q[LL].y]))
86 {
87 LL++;
88 if (LL>500000) LL-=500000;
89 u=Q[LL];
90 }
91 else
92 {
93 L++;
94 u=q[L];
95 if (L>500000) L-=500000;
96 }
97 vis[u.x][u.y]=0;
98 for (i=0;i4;i++)
99 {
100 if (g[i][u.x][u.y]==-1) continue;
101 int x=(g[i][u.x][u.y]-1)/m+1,y=(g[i][u.x][u.y]-1)%m+1;
102 if (f[l][r][x][y]>f[l][r][u.x][u.y]+1)
103 {
104 f[l][r][x][y]=f[l][r][u.x][u.y]+1;
105 if (vis[x][y]==0)
106 {
107 vis[x][y]=1;
108 RR++;
109 if (RR>500000) RR-=500000;
110 Q[RR]=(ZYYS){x,y,f[l][r][x][y]};
111 }
112 }
113 }
114 }
115 }
116 ans=inf;
117 for (i=1;i)
118 for (j=1;j)
119 ans=min(ans,f[1][cnt][i][j]);
120 if (ans==inf) cout1;
121 else
122 coutans;
123 }
[APIO2013]机器人
标签：必须 第一步 mes 解决 radius mem 方向 amp 逆时针
原文地址：https://www.cnblogs.com/Y-E-T-I/p/8909022.html