题意： 给定初始矩阵和目标矩阵 （都是4*4，矩阵元素都为0/1）
只有相邻才能交换
求最少交换多少次使得初始矩阵变为目标矩阵
思路：矩阵里 一定有x个需交换成1的0
也一定有y个需交换成0的1
对于每一个需交换的元素来说
选取最近的与自己不同的待交换的元素交换即可
bfs实现
还有 要知道的很重要的
调换两个元素所需交换的次数为两者的曼哈顿距离（即横坐标之差加上纵坐标之差）
还有啊 这个算法有一个bug 待更正！！！！！！
现在只能先上有bug的code啦
1 #include<iostream> 2 #include<cstdio> 3 #include<string> 4 #include<cstring> 5 #include<queue> 6 #include<cmath> 7 #define go(i,a,b) for(register int i=a;i<=b;i++) 8 #define mem(a,b) memset(a,b,sizeof(a)); 9 using namespace std; 10 int fmap[5][5],lmap[5][5],ans; 11 bool flag[5][5],vis[5][5]; 12 int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1}; 13 string s; 14 struct node {int x,y;}; 15 int bfs(int x,int y) 16 { 17 flag[x][y]=0; 18 queue<node> Q; 19 Q.push((node){x,y}); 20 while(!Q.empty()){ 21 node q=Q.front();Q.pop(); 22 go(i,0,3){ 23 int a=q.x+dx[i],b=q.y+dy[i]; 24 if(a<1||a>4||b<1||b>4||vis[a][b]) continue ; 25 if(flag[a][b]&&lmap[x][y]!=lmap[a][b]) 26 {flag[a][b]=0;return abs(a-x)+abs(b-y);} 27 else {vis[a][b]=1;Q.push((node){a,b});} 28 } 29 } 30 } 31 int main() 32 { 33 34 go(i,1,4){ 35 cin>>s; 36 go(j,1,4) fmap[i][j]=s[j-1]-‘0‘; 37 } 38 go(i,1,4){ 39 cin>>s; 40 go(j,1,4) lmap[i][j]=s[j-1]-‘0‘; 41 } 42 43 go(i,1,4) go(j,1,4) if(fmap[i][j]!=lmap[i][j]) flag[i][j]=1; 44 go(i,1,4) go(j,1,4) if(flag[i][j]) ans+=bfs(i,j),mem(vis,0); 45 printf("%d",ans); 46 return 0; 47 }