今天我做了 POJ 1753 Flip Game 一题。这道题很简单，就是宽度优先搜索。关键是为了提高搜索的速度和判重速度，要使用 位运算哈希加速。
下面是我的代码。
非位运算版（速度很慢，要AC请看位运算版）：
/* * Flip Game (POJ 1753) * URL: http://poj.org/problem?id=1753 * Author: Ceeji Cheng * Type: 枚举 * Status: Sovled * Visit http://ceeji.net/ for more information. * 2010-11-13 * */ #include <iostream> #include <cstring> #define count 4 #define maxlength 20000 typedef short round_status[count][count]; typedef unsigned int uint; using namespace std; void copyarr(round_status &source, round_status &dest) { memcpy(&dest, &source, sizeof(round_status)); } void output(int steps) { cout << steps; } void init(round_status &pstatus) { char c; for (uint i = 0; i < count; ++i) { for (uint j = 0; j < count; ++j) { do { cin >> c; } while (!(c == 'w' || c == 'b')); if (c == 'w') pstatus[i][j] = 0; else pstatus[i][j] = 1; } } } void flip(round_status &pstatus, int x, int y) { pstatus[x][y] = 1 - pstatus[x][y]; if (x > 0) { pstatus[x - 1][y] = 1 - pstatus[x - 1][y]; } if (y > 0) { pstatus[x][y - 1] = 1 - pstatus[x][y - 1]; } if (x < count - 1) { pstatus[x + 1][y] = 1 - pstatus[x + 1][y]; } if (y < count - 1) { pstatus[x][y + 1] = 1 - pstatus[x][y + 1]; } } bool check(round_status &pstatus) { int p = pstatus[0][0]; for (uint i = 0; i < count; ++i) for (uint j = 0; j < count; ++j) if (pstatus[i][j] != p) return false; return true; } bool issame(round_status &status1, round_status &status2) { for (uint i = 0; i < count; ++i) for (uint j = 0; j < count; ++j) if (status1[i][j] != status2[i][j]) return false; return true; } bool hassame(round_status (*status)[maxlength], int pc) { for (int i = 0; i < pc - 1; ++i) { if (issame(*(*status + i), *(*status + pc))) return true; } return false; } /* Find the result. */ void search(round_status &pstatus) { round_status status[maxlength]; int step[maxlength]; int pf = 0, pc = 1; step[0] = 0; copyarr(pstatus, status[0]); do { for (uint i = 0; i < count; ++i) { for (uint j = 0; j < count; ++j) { copyarr(status[pf], status[pc]); flip(status[pc], i, j); if (hassame(&status, pc)) { continue; } if (check(status[pc])) { output(step[pf] + 1); return; } step[pc] = step[pf] + 1; ++pc; if (pc > maxlength - 1) { cout << "Impossible"; return; } } } ++pf; } while ((pf < pc)); cout << "Impossible"; return; } int main(void) { round_status start_status; // start status of the field. init(start_status); if (check(start_status)) { output(0); return 0; } search(start_status); return 0; } |
位运算版，0ms搞定。
/* * Flip Game (POJ 1753) * URL: http://poj.org/problem?id=1753 * Author: Ceeji Cheng * Type: 枚举 + 位运算 * Status: Sovled * Visit http://ceeji.net/ for more information. * 2010-11-13 * */ #include <iostream> #include <cstring> #define count 16 #define rwcount 4 #define bitwidth 16 #define maxlength 65536 #define copyarr(source,dest) dest = source; typedef unsigned short round_status; typedef unsigned int uint; using namespace std; bool used[65536]; void output(int steps) { cout << steps; } void init(round_status &pstatus) { memset(used, 0, sizeof(used)); pstatus = 0; char c; for (uint i = 0; i < count; ++i) { do { cin >> c; } while (!(c == 'w' || c == 'b')); if (c == 'b') pstatus = pstatus | (1 << (15 - i)); } } void flip(round_status &pstatus, int x, int y) { pstatus = pstatus ^ (1 << (bitwidth - (x * rwcount + y) - 1)); if (x > 0) { pstatus = pstatus ^ (1 << (bitwidth - ((x - 1) * rwcount + y) - 1)); } if (y > 0) { pstatus = pstatus ^ (1 << (bitwidth - (x * rwcount + y - 1) - 1)); } if (x < rwcount - 1) { pstatus = pstatus ^ (1 << (bitwidth - ((x + 1) * rwcount + y) - 1)); } if (y < rwcount - 1) { pstatus = pstatus ^ (1 << (bitwidth - (x * rwcount + y + 1) - 1)); } } bool check(round_status pstatus) { return (pstatus == 0 || (~pstatus) == 0 || pstatus == 65535); } bool hassame(round_status status) { return used[status]; } /* Find the result. */ void search(round_status &pstatus) { round_status status[maxlength]; int step[maxlength]; int pf = 0, pc = 1; step[0] = 0; status[0] = pstatus; used[pstatus] = true; do { for (uint i = 0; i < rwcount; ++i) { for (uint j = 0; j < rwcount; ++j) { status[pc] = status[pf]; flip(status[pc], i, j); if (hassame(status[pc])) { continue; } step[pc] = step[pf] + 1; used[status[pc]] = true; if (check(status[pc])) { output(step[pf] + 1); return; } ++pc; if (pc > maxlength - 1) { cout << "Impossible"; return; } } } ++pf; } while ((pf < pc)); cout << "Impossible"; return; } int main(void) { round_status start_status; // start status of the field. init(start_status); if (check(start_status)) { output(0); return 0; } search(start_status); return 0; } |