黑白棋游戲

Description

黑白棋游戲的棋盤是由4 * 4的方格陣列構成。棋盤的每一方格中放有1枚棋子，共有8枚白棋子和8枚黑棋子。這16枚棋子的每一種放置方案都構成一個游戲狀態。在棋盤上擁有1條公共邊的2個方格稱為相鄰方格。一個方格最多可有4個相鄰方格。在玩黑白棋游戲時，每一步可將任何2個相鄰方格中棋子互換位置。對于給定的初始游戲狀態和目標游戲狀態，編程計算從初始游戲狀態變化到目標游戲狀態的最短著棋序列。

Input

輸入共8行。前四行是初始游戲狀態，后四行是目標游戲狀態。每行四個數分別表示該行放置的棋子顏色?！?”表示白棋，“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型，后面是因為搜索中一個變量引用錯誤