企业官网建设流程全解析

题目描述

在一个n×nn \times nn×n的棋盘上放置了nnn个石子，每个格子最多一个石子。每次操作可以将任意一个石子向上、下、左、右移动一个单位，且目标格子必须为空。目标是用最少的移动次数将所有石子排成一条直线，这条直线可以是水平、垂直或对角方向。

输入格式

输入包含多组测试数据。每组数据第一行给出一个整数nnn（1≤n≤151 \le n \le 151≤n≤15），表示棋盘大小和石子数量。接下来一行包含nnn对整数，每对给出一个石子的行号和列号。输入以单独一行的000结束。

输出格式

对每组测试数据，输出一行Board X: Y moves required.，其中XXX为测试数据编号，YYY为最少移动次数。

样例输入

5 1 2 2 4 3 4 5 1 5 3 2 1 1 1 2 3 3 1 1 2 2 2 0

样例输出

Board 1: 6 moves required. Board 2: 0 moves required. Board 3: 1 moves required.

题目分析

本题要求将nnn个石子移动到同一条直线上，使得总移动次数最小。直线可以是nnn种水平线（第111行到第nnn行）、nnn种垂直线（第111列到第nnn列）以及222条对角线（主对角线和副对角线），共2n+22n + 22n+2种可能的直线。对于每一条候选直线，该直线上恰好有nnn个格子，需要将nnn个石子分别移动到这些格子上，每个格子恰好放一个石子。由于石子之间没有区别，问题转化为：给定nnn个石子的初始位置和nnn个目标位置，求一个一一对应的匹配，使得所有石子移动的总曼哈顿距离最小。这是一个经典的指派问题，可以用Kuhn-Munkres\texttt{Kuhn-Munkres}Kuhn-Munkres算法（匈牙利算法）在O(n3)O(n^3)O(n3)时间内求解。

对于每一条候选直线，构造一个n×nn \times nn×n的权值矩阵，其中weight[i][j]\textit{weight}[i][j]weight[i][j]表示第iii个石子移动到该直线上第jjj个目标格子的曼哈顿距离。由于Kuhn-Munkres\texttt{Kuhn-Munkres}Kuhn-Munkres算法通常用于求最大权匹配，而本题要求最小权匹配，因此需要将权值取反或转换为a−weight[i][j]a - \textit{weight}[i][j]a−weight[i][j]的形式（其中aaa为所有权值中的最大值），再求最大权匹配，最后用n×an \times an×a减去匹配结果得到最小总距离。代码中的modifiedKuhnMunkres函数正是实现了这一转换。

枚举所有2n+22n + 22n+2条候选直线，对每条直线计算最小总移动次数，取全局最小值即为答案。时间复杂度为O(n4)O(n^4)O(n4)，因为每条直线需要O(n3)O(n^3)O(n3)的匹配算法，共有O(n)O(n)O(n)条直线。在n≤15n \le 15n≤15的约束下，计算量完全可行。

解题思路

步骤1\texttt{1}1. 读取棋盘大小nnn和nnn个石子的坐标，将坐标存储在两个数组sxsxsx和sysysy中。

步骤2\texttt{2}2. 初始化最小移动次数rrr为无穷大。

步骤3\texttt{3}3. 枚举所有水平线：对于每一行rowrowrow（从111到nnn），构造权值矩阵，其中weight[si][cln−1]=∣sx[si]−row∣+∣sy[si]−cln∣\textit{weight}[si][cln-1] = |sx[si] - row| + |sy[si] - cln|weight[si][cln−1]=∣sx[si]−row∣+∣sy[si]−cln∣，表示第sisisi个石子移动到第rowrowrow行第clnclncln列的曼哈顿距离。调用modifiedKuhnMunkres计算该直线的最小总移动次数，更新rrr。

步骤4\texttt{4}4. 枚举所有垂直线：对于每一列clnclncln（从111到nnn），构造权值矩阵，其中weight[si][row−1]=∣sx[si]−row∣+∣sy[si]−cln∣\textit{weight}[si][row-1] = |sx[si] - row| + |sy[si] - cln|weight[si][row−1]=∣sx[si]−row∣+∣sy[si]−cln∣，表示第sisisi个石子移动到第rowrowrow行第clnclncln列的曼哈顿距离。调用modifiedKuhnMunkres计算最小总移动次数，更新rrr。

步骤5\texttt{5}5. 枚举主对角线：从(1,1)(1,1)(1,1)到(n,n)(n,n)(n,n)，构造权值矩阵，其中weight[si][row−1]=∣sx[si]−row∣+∣sy[si]−row∣\textit{weight}[si][row-1] = |sx[si] - row| + |sy[si] - row|weight[si][row−1]=∣sx[si]−row∣+∣sy[si]−row∣。调用modifiedKuhnMunkres计算最小总移动次数，更新rrr。

步骤6\texttt{6}6. 枚举副对角线：从(n,1)(n,1)(n,1)到(1,n)(1,n)(1,n)，构造权值矩阵，其中weight[si][cln−1]=∣sx[si]−(n−cln+1)∣+∣sy[si]−cln∣\textit{weight}[si][cln-1] = |sx[si] - (n - cln + 1)| + |sy[si] - cln|weight[si][cln−1]=∣sx[si]−(n−cln+1)∣+∣sy[si]−cln∣。调用modifiedKuhnMunkres计算最小总移动次数，更新rrr。

步骤7\texttt{7}7. 输出Board X: r moves required.，其中XXX为测试数据编号。

代码实现

// The Great Wall Game// UVa ID: 1045// Verdict: Accepted// Submission Date: 2019-06-23// UVa Run Time: 0.000s//// 版权所有（C）2019，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constintMAXN=110,INF=0x7f7f7f7f;intlinky[MAXN],cx[MAXN],cy[MAXN];intweight[MAXN][MAXN],lx[MAXN]={0},ly[MAXN]={0},slack;intn;booldfs(intx){cx[x]=true;for(inty=0;y<n;y++){if(cy[y])continue;intdelta=lx[x]+ly[y]-weight[x][y];if(!delta){cy[y]=true;if(linky[y]==-1||dfs(linky[y])){linky[y]=x;returntrue;}}elseslack=min(slack,delta);}returnfalse;}intkuhnMunkres(){memset(linky,-1,sizeof(linky));for(inti=0;i<n;i++){lx[i]=-INF,ly[i]=0;for(intj=0;j<n;j++)lx[i]=max(lx[i],weight[i][j]);}for(intx=0;x<n;x++)while(true){memset(cx,0,sizeof(cx));memset(cy,0,sizeof(cy));slack=INF;if(dfs(x))break;for(inti=0;i<n;i++){if(cx[i])lx[i]-=slack;if(cy[i])ly[i]+=slack;}}intr=0;for(inty=0;y<n;y++)if(~linky[y])r+=weight[linky[y]][y];returnr;}intmodifiedKuhnMunkres(){inta=0;for(inti=0;i<n;i++)for(intj=0;j<n;j++)a=max(a,weight[i][j]);for(inti=0;i<n;i++)for(intj=0;j<n;j++)weight[i][j]=a-weight[i][j];intr=kuhnMunkres();returnn*a-r;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intsx[16],sy[16],cases=0;while(cin>>n,n>0){for(inti=0;i<n;i++)cin>>sx[i]>>sy[i];intr=INF;for(introw=1;row<=n;row++){memset(weight,0,sizeof(weight));for(intcln=1;cln<=n;cln++)for(intsi=0;si<n;si++)weight[si][cln-1]=abs(sx[si]-row)+abs(sy[si]-cln);r=min(r,modifiedKuhnMunkres());}for(intcln=1;cln<=n;cln++){memset(weight,0,sizeof(weight));for(introw=1;row<=n;row++)for(intsi=0;si<n;si++)weight[si][row-1]=abs(sx[si]-row)+abs(sy[si]-cln);r=min(r,modifiedKuhnMunkres());}memset(weight,0,sizeof(weight));for(introw=1,cln=1;row<=n;row++,cln++)for(intsi=0;si<n;si++)weight[si][row-1]=abs(sx[si]-row)+abs(sy[si]-cln);r=min(r,modifiedKuhnMunkres());memset(weight,0,sizeof(weight));for(introw=n,cln=1;cln<=n;row--,cln++)for(intsi=0;si<n;si++)weight[si][cln-1]=abs(sx[si]-row)+abs(sy[si]-cln);r=min(r,modifiedKuhnMunkres());cout<<"Board "<<++cases<<": "<<r<<" moves required.\n";cout<<'\n';}return0;}

总结

本题的关键在于将石子排成一条直线的问题转化为指派问题。对于每一条候选直线，直线上恰好有nnn个目标格子，需要将nnn个石子一一匹配到这些格子上，使得总曼哈顿距离最小。使用Kuhn-Munkres\texttt{Kuhn-Munkres}Kuhn-Munkres算法可以在O(n3)O(n^3)O(n3)时间内求出最小权匹配。由于候选直线只有2n+22n + 22n+2条，总时间复杂度为O(n4)O(n^4)O(n4)，在n≤15n \le 15n≤15的范围内完全可行。需要注意Kuhn-Munkres\texttt{Kuhn-Munkres}Kuhn-Munkres算法通常求解最大权匹配，因此需要将最小权匹配转换为最大权匹配，代码中通过a−weight[i][j]a - \textit{weight}[i][j]a−weight[i][j]的方式实现。最终取所有候选直线中的最小值即为答案。