和bzoj2595类似，也是斯坦纳树

设f[l,r,]表示在点i机器人组合成了l-r最少推的次数，然后可得

f[l,r,i]=min(f[l,m,i]+f[m+1,r,i])

f[l,r,i]=min(f[l,r,j]+1) 点j能推到i

但是这样做肯定会TLE，考虑两个优化

首先，一开始其实有很多根本用不到，我们可以先从机器人初始位置搜下去，找到所有可以访问的点做dp即可

其次，观察第二个方程，它的边权都是1，我们一定要用spfa转移吗？不，我们可以用直接宽搜

具体的我们维护两个队列，第一个队列是初始的按从小到大排，新加入的点放在第二个队列，每次取两个队头小的那一个

但我还是tle，求神犇指教

1 const dx:array[1..4] of longint=(0,1,0,-1);  2       dy:array[1..4] of longint=(1,0,-1,0);  3       inf=1000000007;  4 type node=record  5        x,y:longint;  6      end;  7   8 var w:array[0..250010] of node;  9     q1,q2,st:array[0..250010] of longint; 10     po:array[0..501,0..501,1..4] of longint; 11     f:array[0..250010,0..9,0..9] of longint; 12     c:array[0..501,0..501] of char; 13     v:array[0..250010] of boolean; 14     loc:array[0..250010] of longint; 15     next:array[0..250010,1..4] of longint; 16     s:array[0..100010] of longint; 17     mid,h1,t1,i,j,p,q,l,x,y,k,n,m,ans,mx,tot:longint; 18  19 function min(a,b:longint):longint; 20   begin 21     if a>b then exit(b) else exit(a); 22   end; 23  24 function dfs(x,y,k:longint):longint; 25   var xx,yy:longint; 26   begin 27     if (po[x,y,k]=0) then exit(-1); 28     if po[x,y,k]>0 then exit(po[x,y,k]); 29     po[x,y,k]:=0; 30     xx:=x+dx[k]; 31     yy:=y+dy[k]; 32     if (xx<1) or (xx>n) or (yy<1) or (yy>m) or (c[xx,yy]='x') then po[x,y,k]:=(x-1)*m+y 33     else if c[xx,yy]='A' then po[x,y,k]:=dfs(xx,yy,(k+2) mod 4+1) 34     else if c[xx,yy]='C' then po[x,y,k]:=dfs(xx,yy,k mod 4+1) 35     else po[x,y,k]:=dfs(xx,yy,k); 36     exit(po[x,y,k]); 37   end; 38  39 function cmp(i,j,l,r:longint):boolean; 40   begin 41     exit(f[i,l,r]
      
       t2) or (h1<=t1) and cmp(q1[h1],q2[h2],l,r) then 64       begin 65         x:=q1[h1]; 66         inc(h1); 67       end 68       else begin 69         x:=q2[h2]; 70         inc(h2); 71       end; 72       v[x]:=true; 73       for i:=1 to 4 do 74       begin 75         if next[x,i]=0 then continue; 76         y:=next[x,i]; 77         if not v[y] and (f[x,l,r]+1
       
        ='1') and (c[i,j]<='9') then100       begin101         x:=ord(c[i,j])-48;102         inc(t1);103         w[t1].x:=i; w[t1].y:=j;104         f[t1,x,x]:=0;105         loc[(i-1)*m+j]:=t1;106       end;107     end;108     readln;109   end;110   fillchar(po,sizeof(po),255);111   h1:=1;112   while h1<=t1 do113   begin114     x:=w[h1].x; y:=w[h1].y;115     for i:=1 to 4 do116     begin117       if po[x,y,i]=-1 then118       begin119         po[x,y,i]:=dfs(x,y,i);120         if (po[x,y,i]>0) and (loc[po[x,y,i]]=0) then121         begin122           inc(t1);123           w[t1].x:=(po[x,y,i]-1) div m+1;124           w[t1].y:=(po[x,y,i]-1) mod m+1;125           loc[po[x,y,i]]:=t1;126         end;127       end;128       if po[x,y,i]>0 then next[h1,i]:=loc[po[x,y,i]];129     end;130     inc(h1);131   end;132   tot:=t1;133   for l:=1 to k do134     for p:=1 to k-l+1 do135     begin136       q:=p+l-1;137       h1:=1; t1:=0; mx:=0;138       for i:=1 to tot do139       begin140         v[i]:=false;141         for mid:=p to q-1 do142           f[i,p,q]:=min(f[i,p,q],f[i,p,mid]+f[i,mid+1,q]);143         if f[i,p,q]
        
         mx then mx:=f[i,p,q];149         end;150       end;151       sort(p,q);152       for i:=0 to mx do153         s[i]:=0;154       bfs(p,q);155     end;156   ans:=inf;157   for i:=1 to tot do158     ans:=min(ans,f[i,1,k]);159   if ans>=inf then writeln(-1)160   else writeln(ans);     161 end.