poj1753解题报告

1.算法
核心是宽度优先搜索和位处理。要找出最快的步数，用宽搜。
(1)宽度优先搜索数据结构：
队列的单元unit包含x（用int的末16位记录16个位置的信息），rounds（记录第几轮达到当前的状态），i（记录该状态是通过翻动哪个棋子得来的，以避免返回先前的状态）。queue是一个队列，记录所有状态；p，q分别是队列的头尾指针。used记录已经存在的状态。
(2)宽度优先搜索算法处理：
a.首先是读入数据。
b.进行宽度搜索，直到找到结果，或者队列中没有元素（此时为impossible）。
c.flip函数是从a状态通过翻动第i个棋子到达b状态。
d.在得到一个新状态的时候要检验之前时候存在这个状态，如果存在就把这个状态舍弃，即q--；
2.实现
(1)阅读代码的时候，不能scanf("%c")读取到每一个字符，因为读取字符的时候会读到"\n"，或许还会有其他的字符。通过读取string能够解决这个问题。
(2)通过位操作可以a.减少内存b.可以对16位单独操作，也可以对整体进行操作。
(3)在查找某状态是否与之前状态有重叠时可以通过数组下标进行操作，这样速度较快。
(4)获取一个int某位用该int与(0X1<<i)进行&操作。
   将一个int的某位置1用该int与(0X1<<i)进行|操作。
   将一个int的某位置反用该int与(0X1<<i)进行^操作。
3. 代码
#include<cstdio>

struct unit {
int x;
int rounds;
int i;
};

void flip(unit a, int n, unit& b);

int main() {
/*queue*/
unit queue[100000];
queue[0].x = 0;
queue[0].i = -1;
queue[0].rounds = 0;
int p = 0, q = 0;
//judge used
bool 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] == 'b') {
queue[0].x = ((0X1 << (i * 4 + j)) | (queue[0].x));
}
}
}
/*search*/

while (!((queue[q].x == 0) || (queue[q].x == 0XFFFF))) {
for (int i = 0; i < 16; i++) {
if(queue[p].i==i) continue;
q++;
flip(queue[p], i, queue[q]);
if (used[queue[q].x])q--;
used[queue[q].x]=true;
if ((queue[q].x == 0) || (queue[q].x == 0XFFFF))
break;
}

if (p == q) {
printf("Impossible");
break;
}

p++;
}
if ((queue[q].x == 0) || (queue[q].x == 0XFFFF))
printf("%d\n", queue[q].rounds);
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)));
if (x > 0)
b.x = ((b.x) ^ (0X1 << (n - 4)));
if (x < 3)
b.x = ((b.x) ^ (0X1 << (n + 4)));
if (y > 0)
b.x = ((b.x) ^ (0X1 << (n - 1)));
if (y < 3)
b.x = ((b.x) ^ (0X1 << (n + 1)));
b.rounds = a.rounds + 1;
b.i = n;
}