poj2965解题报告
这道题目的思路和poj1753的思路一样。
有所不同的是这道题目中还需要输出搜索的路径，于是在unit中加了一个pre变量以记录搜索的路径，最后通过递归调用print_detail从前往后输出宽搜的结果。

Problem: 2965User: godfrey90Memory: 1992KTime: 1000MSLanguage: G++Result: AcceptedSource Code#include<cstdio>struct unit {int x;int rounds;int i;int pre;};void flip(unit a, int n, unit& b);void print_detail(unit queue[], int n);int main() {/*queue*/unit queue[100000];queue[0].x = 0;queue[0].i = -1;queue[0].rounds = 0;queue[0].pre=-1;int p = 0, q = 0;//judge usedbool used[100000] = { false };/*read in*/char str[10];for (int i = 0; i < 4; i++) {scanf("%s", str);for (int j = 0; j < 4; j++) {if (str[j] == '+') {queue[0].x = ((0X1 << (i * 4 + j)) | (queue[0].x));}}}/*search*/while (!(queue[q].x == 0)) {for (int i = 0; i < 16; i++) {if (queue[p].i == i)continue;q++;flip(queue[p], i, queue[q]);queue[q].pre = p;if (used[queue[q].x])q--;used[queue[q].x] = true;if (queue[q].x == 0)break;}if (p == q) {printf("Impossible");break;}p++;}if (queue[q].x == 0)printf("%d\n", queue[q].rounds);print_detail(queue,q);return 0;}void flip(unit a, int n, unit& b) {int x = n / 4, y = n % 4;b.x = a.x;b.x = ((b.x) ^ (0X1 << (n)));b.x = ((b.x) ^ (0X1 << (y)));b.x = ((b.x) ^ (0X1 << (y+4)));b.x = ((b.x) ^ (0X1 << (y+4*2)));b.x = ((b.x) ^ (0X1 << (y+4*3)));b.x = ((b.x) ^ (0X1 << (4*x)));b.x = ((b.x) ^ (0X1 << (4*x+1)));b.x = ((b.x) ^ (0X1 << (4*x+2)));b.x = ((b.x) ^ (0X1 << (4*x+3)));b.rounds = a.rounds + 1;b.i = n;}void print_detail(unit queue[], int n){if(queue[n].pre==-1) return;print_detail(queue,queue[n].pre);int x,y;x=queue[n].i/4+1;y=queue[n].i%4+1;printf("%d %d\n",x,y);}