2006CQOI移动棋子BYRJ【2006重庆】移动棋子【题目简述】：N*N的棋盘上有N个棋子，M个障碍，一开始棋子和障碍不会在同一格，棋子可以向上下左右移动，但不能到有障碍的格子，现在要将所有的棋子移到同一行或同一列或正副对角线，要求求出最短移动距离。【题目简析】：分析每一种目标状态和原始状态，可以发现每一个棋子只会占用一个格子，每一个格子里只有一个棋子，每一个棋子都是从一个格子移动到令一个格子，并且两个格子之间互不影响。如果把棋子的原始位置看做X集，目标位置看做Y集，每一个棋子能且仅能从X集中的一个格子到Y集之中的一个格子，这样就构成了二分图匹配，以两个格子之间的最短距离为权值，移动距离最小的方案就是二分图的最小权完备匹配。直接用KM算法可以解决。【算法流程】：1.宽搜求得每一个棋子到其他位置的最短距离。2.枚举2N+2种可能的Y集，构建二分图，求最小权完备匹配。3.比较每一种结果，取最小值。【注意事项】：如果Y集中有障碍，则该目标位置集合不存在，可直接跳过；如果没有一种可能的Y集，那问题自然无解，输出-1；【时间复杂度分析】：宽搜共O（N）次，每次O（N^2）,共O（N^3）；每次KM为O（N^3），共计执行KMO（2*N+2）次，总的时间复杂度为O（N^4）;N为50，完全可以接受。考虑到实际情况下不可能计算2*N+2次KM，所以实际速度理应比理论上快。我的程序完成所有测试点只用了60MS。【参考代码】：/*Author:rj;Problem:moveLanguage:C++;Meno:二分图最小权匹配*/#include<iostream>usingnamespacestd;constintoo=0x7fffffff/2;intN,ans=oo;intpoint[55][55],dis[55][2555],map[55][55];intdx[]={0,0,1,-1},dy[]={1,-1,0,0},Lx[55],Ly[55],my[55];structNode{intx,y;}a[55],b[55];structQue{intx,y,s;}q[2555];boolstone[55][55]={0},vis[55][55],vx[55],vy[55];voidInit(){intM,i,j,x,y;scanf("%d%d",&N,&M);for(i=1;i<=N;i++)for(j=1;j<=N;j++)point[i][j]=(i-1)*N+j;for(i=1;i<=N;i++)scanf("%d%d",&a[i].x,&a[i].y);whileMade(M--){scanf("%d%d",&x,&y);stone[x][y]=1;}ByRj}voidBFS(intp){intl=0,r=0,i,tx,ty;memset(vis,0,sizeof(vis));http://blog.sina.com.cn/letsgoahead2006CQOI移动棋子BYRJq[0].x=a[p].x;q[0].y=a[p].y;q[0].s=0;vis[a[p].x][a[p].y]=1;dis[p][point[a[p].x][a[p].y]]=0;while(l<=r){for(i=0;i<4;i++){tx=q[l].x+dx[i];ty=q[l].y+dy[i];if(vis[tx][ty]||tx>N||tx<1||ty>N||ty<1)continue;if(stone[tx][ty]){dis[p][point[tx][ty]]=oo;continue;}vis[tx][ty]=1;r++;q[r].x=tx;q[r].y=ty;q[r].s=q[l].s+1;dis[p][point[tx][ty]]=q[r].s;}l++;}}voidPre(){inti,j;for(i=1;i<=N;i++)BFS(i);}voidBuildGraph(){inti,j;for(i=1;i<=N;i++)for(j=1;j<=N;j++)map[i][j]=dis[i][point[b[j].x][b[j].y]];}voidAdjust(){inti,j,delta=oo;for(i=1;i<=N;i++)if(vx[i])for(j=1;j<=N;j++)if(!vy[j])if(delta>map[i][j]-(Lx[i]+Ly[j]))delta=map[i][j]-(Lx[i]+Ly[j]);for(i=1;i<=N;i++)