题目描述

在一个 4×4 的棋盘上有88 个黑棋和 88 个白棋，当且仅当两个格子有公共边，这两个格子上的棋是相邻的。移动棋子的规则是交换相邻两个棋子。

给出一个初始棋盘和一个最终棋盘，请找出一个最短的移动序列使初始棋盘变为最终棋盘。

输入

前四行，每行 4 个数字（1 或者 0），描述了初始棋盘；

接着是一个空行；

讯享网

第六到第九行，每行 4 个数字（1 或者0），描述了最终棋盘

输出

一行是一个整数 nn，表示最少的移动步数。

输入样例

1111 0000 1110 0010 1010 0101 1010 0101 

输出样例

4

思路

采用bfs的思路：为了简便计算， 发现输入的棋盘是用0和1来表示的，大小也固定为4*4，所以我们可以用16位二进制来表示这个棋盘,为了方便我们将第一个数作为最高位，以此类推。通过（异或）+（与）运算判断二进制位是否需要交换。 广搜的思路是——将交换1/2/3/4.。。。次可以形成的棋盘记录并加入队列，符合最终棋盘的就将其交换次数输出

讯享网#include <cstring> #include <iostream> #include <queue> using namespace std; struct f { int sum; int b; }; int book[70000]; int ans1; int ans2; queue<f>que; int bfs() { struct f a, s; a.sum = ans1; a.b = 0; que.push(a); int h, j; int x, y, t, z,i; while (!que.empty()) { //特别注意需要在开头加这个条件否则如果ans1起始就等于ans2会出现错误 if (a.sum == ans2) return a.b; int temp = a.sum; for ( i = 15; i >= 0; i--) { s = a;//因为每一次for循环都是在队首元素的基础上多交换一次进行的，所以需要每次将s更新成为队首元素，不然无法做到将交换1/2/3.。。次形成的全部情形记录 //此方法可得出其横坐标 x 和纵坐标 y x = (15 - i) / 4, y = (15 - i) % 4, t = 1 << i,z; h = (temp & (1 << i))>>i;//通过左移和右移运算可以将其i和i-4位分离出来用于下面的比较 j = (temp & (1 << (i - 4)))>>(i-4); //左右交换 if (x < 3 && (h!=j)) { //不相等的话就交换一次 z = 1 << (i - 4); if (book[temp ^ t ^ z]==0) { book[temp^ t ^ z] = 1; s.sum = temp ^ t ^ z;//通过异或运算可以交换二进制的i位和i-4位 s.b++; que.push(s); s.b--;//特别注意 } } if (s.sum == ans2) return s.b+1;//如果符合要求就返回 j = (temp & (1 << (i - 1)))>>(i-1); //上下交换 if (y < 3 && (h!=j)) { //不相等的话就交换一次 z = 1 << (i - 1); if (book[temp ^ t ^ z]==0) { book[temp ^ t ^ z] = 1; s.sum = temp ^ t ^ z; s.b++; que.push(s); } } if (s.sum == ans2) return s.b; } que.pop();//得出交换s.b次可以得到的棋盘后，将队列首元素弹出，然后进入循环将交换s.b+1次可以形成的棋盘二进制形式加入队列 a = que.front(); } } int main(void) { char c; int i; for (i = 15; i >= 0; i--) { cin >> c; if (c == '1') ans1 += (1 << i);//左移运算得出二进制表示的十进制数字 } for (i = 15; i >= 0; i--) { cin >> c; if (c == '1') ans2 += (1 << i); } cout<<bfs()<<endl; return 0; } 

输入路径（数组实现队列）

#include <cstring> #include <iostream> #include <queue> #include <cstdio> using namespace std; struct f { int sum; int b; int f; int x; int y; int nx;//x,y和nx,ny为交换的两个棋子坐标 int ny; }que[70000]; int book[70000]; int ans1; int ans2; void print(int x) { if (que[x].f != -1) { print(que[x].f); printf("(%d,%d)<-->(%d,%d)\n", que[x].x, que[x].y, que[x].nx, que[x].ny); } } int bfs() { int head = 1, tail = 1; que[head].sum = ans1; que[head].b = 0; que[head].f = -1; tail++; int h, j; int x, y, t, z,i; while (head<tail) { if (que[head].sum == ans2) { //注意不能忽略 print(head); printf("(%d,%d)<-->(%d,%d)\n", que[tail].x, que[tail].y, que[tail].nx, que[tail].ny); return que[head].b; } int temp = que[head].sum; for ( i = 15; i >= 0; i--) { x = (15 - i) / 4, y = (15 - i) % 4, t = 1 << i,z; h = (temp & (1 << i))>>i; j = (temp & (1 << (i - 4)))>>(i-4); if (x < 3 && (h!=j)) { z = 1 << (i - 4); if (book[temp ^ t ^ z]==0) { book[temp^ t ^ z] = 1; que[tail].sum = temp ^ t ^ z; que[tail].b=que[head].b+1; que[tail].x = x; que[tail].y = y; que[tail].nx = x + 1; que[tail].ny = y; que[tail].f = head;//记录父亲点的标号 if (que[tail].sum == ans2) { print(head); printf("(%d,%d)<-->(%d,%d)\n", que[tail].x, que[tail].y, que[tail].nx, que[tail].ny); return que[tail].b; } tail++; } } j = (temp & (1 << (i - 1)))>>(i-1); if (y < 3 && (h!=j)) { z = 1 << (i - 1); if (book[temp ^ t ^ z]==0) { book[temp ^ t ^ z] = 1; que[tail].sum = temp ^ t ^ z; que[tail].b=que[head].b + 1; que[tail].x = x; que[tail].y = y; que[tail].nx = x; que[tail].ny = y+1; que[tail].f = head; if (que[tail].sum == ans2) { print(head); printf("(%d,%d)<-->(%d,%d)\n", que[tail].x, que[tail].y, que[tail].nx, que[tail].ny); return que[tail].b; } tail++; } } } head++; } } int main(void) { char c; int i; for (i = 15; i >= 0; i--) { cin >> c; if (c == '1') ans1 += (1 << i); } for (i = 15; i >= 0; i--) { cin >> c; if (c == '1') ans2 += (1 << i); } cout<<bfs()<<endl; return 0; }