题目描述
• 一个 4 × 4 的 0/1 矩阵
• 每次可以交换相邻两个元素
• 求从初始状态到目标状态的最小交换次数
输入格式
前四行,每行一个长为 4 的 0/1 字符串,描述初始状态。
后四行,每行一个长为 4 的 0/1 字符串,描述目标状态。
输出格式
一行一个数,表示最小交换次数。
样例输入
1111
0000
1110
0010
1010
0101
1010
0101
样例输出
4
solution：
不得不说这确实是道好题,而且难度适中。看到此题为0/1字符串并且数据规模小（但也太小了吧）可以想到状压因为只有16个格子，所以不同的局面最多只有2^16 = 65536 个，不过01数量对等所以准确的说应该只有12870 个。所以我们Hash ：把 16 个格子的 0/1 压成一个数字就好了。
但如果仔细分析一下题目性质，我们可以发现一些不同：我们在读入目标棋盘的时候，把当前位置的数和目标棋盘进行比较，如果不一样，比如当前是1，目标是0，那么我们就把当前位置加入move队列里去，否则加入got队列里去。move和got的队列肯定是一样长的。然后我们将这两个队列里的元素进行匹配，把move里的一个位置上的1移到got里的一个位置上去，该操作需要的步数，就是这两个位置的曼哈顿距离。
这样我们可以搜索来枚举匹配方案，当然也可以直接带权二分图匹配（这样可以应对数据范围很大的题型）
code：
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int
using namespace std;
struct su{
int x,y;
}a[101],b[101];
int n,m,t1,t2,ans=inf;
bool c[11][11];
bool d[11][11];
int s[101][101];
bool use[101];
inline int qr(){ char ch;
while((ch=getchar())<'0'||ch>'9');
return ch^48;
}
inline void dfs(int t,int tot){
if(t==t1+1){
ans=tot;
return ;
}
for(rg i=1;i<=t2;++i){
if(use[i]||tot+s[t][i]>ans)
continue;
use[i]=1;
dfs(t+1,tot+s[t][i]);
use[i]=0;
}
}
int main(){
//freopen("game.in","r",stdin);
//freopen("game.out","w",stdout);
n=m=4;
for(rg i=0;i<n;++i)
for(rg j=0;j<m;++j)
c[i][j]=qr();
for(rg i=0;i<n;++i){
for(rg j=0;j<m;++j){
d[i][j]=qr();
if(c[i][j]^d[i][j]){
if(c[i][j]){
a[++t1].x=i;
a[t1].y=j;
}else{
b[++t2].x=i;
b[t2].y=j;
}
}
}
} rg x,y;
for(rg i=1;i<=t1;++i){
for(rg j=1;j<=t2;++j){
x=a[i].x-b[j].x;
y=a[i].y-b[j].y;
if(x<0)x=-x;
if(y<0)y=-y;
s[i][j]=x+y;
}
} dfs(1,0);
printf("%d",ans);
return 0;
}