黑白棋游戏

Description

黑白棋游戏的棋盘是由4 * 4的方格阵列构成。棋盘的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。这16枚棋子的每一种放置方案都构成一个游戏状态。在棋盘上拥有1条公共边的2个方格称为相邻方格。一个方格最多可有4个相邻方格。在玩黑白棋游戏时，每一步可将任何2个相邻方格中棋子互换位置。对于给定的初始游戏状态和目标游戏状态，编程计算从初始游戏状态变化到目标游戏状态的最短着棋序列。

Input

输入共8行。前四行是初始游戏状态，后四行是目标游戏状态。每行四个数分别表示该行放置的棋子颜色。“0”表示白棋，“1”表示黑棋。

Output

输出的第一行是着棋步数n。接下来n行，每行4个数分别表示该步交换棋子的两个相邻方格的位置。例如，abcd表示棋盘上（a，b）处的棋子与（c，d）处的棋子换位。

Sample Input

1111 0000 1110 0010 1010 0101 1010 0101

Sample Output

4 1222 1424 3242 4344

Hint

输出的时候注意数据字典序的问题

Solution

状态压缩，bfs讨论每一种情况，暴力搜索

Code

#include <cstdio>#include <queue>#include <iostream>#define LL long longusing namespace std;queue <int> bfs, ans;int be, e, x;int vis[(1 << 17)];int PRe[(1 << 20)][3];inline bool pd(int num, int x, int y) {  int a = num >> (16 - x) & 1, b = num >> (16 - y) & 1;  if (a != b) return 1; return 0;}inline int exchange1(int num, int x, int y) {  int a = num >> (16 - x) & 1, b = num >> (16 - y) & 1;  return num - (a << (16 - x)) - (b << (16 - y)) + (a << (16 - y)) + (b << (16 - x));}inline int exchange2(int x) {  if (x == 0 || x == 4 || x == 8 || x == 12) return 1;  if (x == 1 || x == 5 || x == 9 || x == 13) return 2;  if (x == 2 || x == 6 || x == 10 || x == 14) return 3;  if (x == 3 || x == 7 || x == 11 || x == 15) return 4;}inline int exchange3(int x) {  if (x == 0 || x == 1 || x == 2 || x == 3) return 1;  if (x == 4 || x == 5 || x == 6 || x == 7) return 2;  if (x == 8 || x == 9 || x == 10 || x == 11) return 3;  if (x == 12 || x == 13 || x == 14 || x == 15) return 4;}inline void print(int d) {  if (pre[d][0]) print(pre[d][0]);  if (pre[d][0]) printf("%d%d%d%d/n", exchange3(pre[d][1]), exchange2(pre[d][1]), exchange3(pre[d][2]), exchange2(pre[d][2]));}int main() {  for (int i = 0; i < 16; ++i) scanf("%1d", &x), be |= x, be <<= 1;  for (int i = 0; i < 16; ++i) scanf("%1d", &x), e |= x, e <<= 1;  bfs.push(be), ans.push(0);  vis[be] = 1;  do {    int temp = bfs.front();    int s = ans.front();    if (temp == e) break;    for (int i = 0; i < 15; ++i) {      if (i == 3 || i == 7 || i == 11) {	if (pd(temp, i, i + 4)) {	  x = exchange1(temp, i, i + 4);	  if (!vis[x]) {	    vis[x] = 1, bfs.push(x), ans.push(s + 1);	    pre[x][0] = temp, pre[x][1] = i, pre[x][2] = i + 4;	  }	}	continue;      }      if (i == 14 || i == 13 || i == 12) {	if (pd(temp, i, i + 1)){	  x = exchange1(temp, i, i + 1);	  if (!vis[x]) {	    vis[x] = 1, bfs.push(x), ans.push(s + 1);	    pre[x][0] = temp, pre[x][1] = i, pre[x][2] = i + 1;	  }	}	continue;      }      if (pd(temp, i, i + 4)) {	x = exchange1(temp, i, i + 4);	if (!vis[x]) {	  vis[x] = 1, bfs.push(x), ans.push(s + 1);	  pre[x][0] = temp, pre[x][1] = i, pre[x][2] = i + 4;	}      }      if (pd(temp, i, i + 1)) {	x = exchange1(temp, i, i + 1);	if (!vis[x]) {	  vis[x] = 1, bfs.push(x), ans.push(s + 1);	  pre[x][0] = temp, pre[x][1] = i, pre[x][2] = i + 1;	}      }    }    ans.pop(), bfs.pop();  }while(1);  int w = ans.front();  printf("%d/n", w);  print(e);  return 0;}
Summary
这道题调了一个下午，一开始是因为vis数组定以成了bool型，后面是因为搜索中一个变量引用错误