传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3205
思路：类似斯坦纳树的想法
但是因为这里的合并必须连号
所以子集枚举就变成了区间合并
说说做法好了
首先记搜搜出每个点向四个方向走一步会到哪里
注意：转向器可能导致机器人一直在里面转出不来，要特判掉
然后设f[l][r][x][y]表示当前合并的机器人是[l,r]，合并点是(x,y)
两种转移：
枚举子区间，合并f[l][r][x][y]=min(f[l][mid][x][y],f[mid+1][r][x][y])
从另一个地方转移过来f[l][r][x][y]=min(f[l][r][xx][yy]) (xx,yy)走一步能到(x,y)
然后还不够
第二种转移的spfa要加一个杂技优化
“
观察这个图 发现所有边的边权都是1 如果是单源的话SPFA可以进化成广搜
现在是多源 因此我们可以这样做：
维护两个队列，将初始所有的点按照距离排序后从小到大加入队列1
每次拓展出的点加入队列2
每次取出点的时候，如果队列1队尾元素的距离小于队列2 就把队列1的队尾元素拿去松弛 否则就用队列2的
这样做之后除了排序之外复杂度是线性的
排序的log可以用计数排序省掉，但是直接sort也能过，无妨
然后这题就搞掉了。。。。。。
”
------以上内容来自popoqqq的博客
然后就卡过了
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define id(x,y) id[x][y]
const int maxn=505,maxk=10,maxb=maxn*maxn,inf=1e9;
const int dx[]={-1,0,1,0};
const int dy[]={0,1,0,-1};
using namespace std;
int n,h,w,next[maxb][4],pos[maxk],f[maxk][maxk][250005],cnt,ans,*dist,id[maxn][maxn],q1[maxb*10],q2[maxb*10];
bool bo[maxb],vis[maxb][4];char map[maxn][maxn];
//inline int id(int x,int y){return x*(h+1)+y;}
inline bool ok(int x,int y){return x>0&&x<=w&&y>0&&y<=h&&map[x][y]!='x';}
inline void decode(int s,int &x,int &y){x=(s-1)/h+1,y=(s-1)%h+1;}
inline bool cmp(int x,int y){return dist[x]<dist[y];}
void dfs(int x,int y,int d){
int s=id(x,y);
if (vis[s][d]) return;
vis[s][d]=1;
next[s][d]=-1;
int nx=x+dx[d],ny=y+dy[d];//printf("%d %d %d
",x,y,d);
if (!ok(nx,ny)) {next[id(x,y)][d]=id(x,y);return;}
int newd=d;
if (map[nx][ny]=='A') newd=(newd+3)%4;
if (map[nx][ny]=='C') newd=(newd+1)%4;
dfs(nx,ny,newd);
next[s][d]=next[id(nx,ny)][newd];
}
void init(){
scanf("%d%d%d",&n,&h,&w);
for (int i=1;i<=w;i++){
scanf("%s",map[i]+1);
for (int j=1;j<=h;j++){
id(i,j)=++cnt;
if (isdigit(map[i][j])) pos[map[i][j]-'0']=id(i,j);
// printf("%d ",id[i][j]);
}
}
//for (int i=1;i<=n;i++) printf("%d
",pos[i]);
}
void bfs(int *d){
int h1=0,t1=-1,h2=0,t2=-1;
dist=d;
for (int i=1;i<=cnt;i++) if (dist[i]!=inf) q2[++t2]=i;//printf("dist=%d
",i);
memset(bo,0,sizeof(bo));
sort(q2,q2+1+t2,cmp);
while (h1<=t1||h2<=t2){
//puts("%p");
int s,x,y;
if (h1>t1) s=q2[h2++];
else if (h2>t2) s=q1[h1++];
else{
if (dist[q1[h1]]<dist[q2[h2]]) s=q1[h1++];
else s=q2[h2++];
}
decode(s,x,y);//printf("%d %d %d
",s,x,y);
bo[s]=1;
for (int i=0;i<4;i++){
int ns=next[s][i];
if (ns!=-1&&dist[ns]>dist[s]+1){
dist[ns]=dist[s]+1;
bo[ns]=1,q1[++t1]=ns;
}
}
while (h2<=t2&&bo[q2[h2]]) h2++;
}
}
void work(){
for (int i=1;i<=w;i++)
for (int j=1;j<=h;j++)
if (map[i][j]!='x')
for (int d=0;d<4;d++)
dfs(i,j,d);
//dfs(1,1,3);for (;;);
/* for (int k=0;k<4;k++,puts("
"))
for (int i=1;i<=w;i++,puts(""))
for (int j=1;j<=h;j++){
//int x,y;decode(next[id(i,j)][k],x,y);
printf("%d ",next[id(i,j)][k]);
// printf("(%d,%d) ",x,y);
}*/
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
for (int k=1;k<=cnt;k++) f[i][j][k]=inf;
for (int i=1;i<=n;i++)
f[i][i][pos[i]]=0;
for (int len=1;len<=n;len++)
for (int l=1;l+len-1<=n;l++) {
int r=l+len-1;
for (int mid=l;mid<r;mid++)
for (int p=1;p<=cnt;p++) f[l][r][p]=min(f[l][r][p],f[l][mid][p]+f[mid+1][r][p]);
//printf("%d ",f[l][r][1]);
//printf("%d %d
",l,r);
bfs(f[l][r]);
}
ans=inf;
for (int i=1;i<=cnt;i++) ans=min(ans,f[1][n][i]);
printf("%d
",ans==inf?-1:ans);
}
int main(){
init(),work();
return 0;
}
/*
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/