可以说这道题和 POJ 1753 特别相似,唯一不同的是,这道题改变了翻转方法,如果直接位运算 + BFS,会稍微有一点点超时。
所以,这次我采用了非算法方面的优化,直接通过下面的方法将题目的时间减少了50%:
1、用宏彻底消除了几乎所有函数的调用开支。
2、使用非同步读写优化读写速度(见代码注释)。
/* * Flip Game (POJ 2965) * URL: http://poj.org/problem?id=2965 * Author: Ceeji Cheng * Type: 枚举 + 位运算 * Status: Sovled * Visit http://ceeji.net/ for more information. * 2010-11-14 * */ #include <iostream> #include <cstring> #define count 16 #define rwcount 4 #define bitwidth 16 #define maxlength 65538 #define copyarr(source,dest) dest = source; #define flip(pstatus, x, y) \ for (unsigned int ii = 0; ii < rwcount; ii += 1) \ { \ pstatus = pstatus ^ (1 << (bitwidth - (x * rwcount + ii) - 1)); \ } \ for (unsigned int ii = 0; ii < rwcount; ii += 1) \ { \ pstatus = pstatus ^ (1 << (bitwidth - (ii * rwcount + y) - 1)); \ } \ pstatus = pstatus ^ (1 << (bitwidth - (x * rwcount + y) - 1)); #define output(steps) \ cout << steps; #define check(pstatus) (pstatus == 0) #define hassame(status) used[status] typedef unsigned short round_status; typedef unsigned int uint; using namespace std; bool used[maxlength]; void init(round_status &pstatus) { std::ios::sync_with_stdio(false); // 优化读入速度。 memset(used, 0, sizeof(used)); pstatus = 0; char c; for (uint i = 0; i < count; ++i) { do { cin >> c; } while (!(c == '-' || c == '+')); if (c == '+') pstatus = pstatus | (1 << (15 - i)); } } void output_detail(int p, round_status (&status)[maxlength], int (&cx)[maxlength], int (&cy)[maxlength], int (&father)[maxlength]) { if (p <= 0) return; output_detail(father[p], status, cx, cy, father); cout << cx[p] + 1 << ' ' << cy[p] + 1 << endl; } /* Find the result. */ void search(round_status &pstatus) { round_status status[maxlength]; int step[maxlength], father[maxlength], cx[maxlength], cy[maxlength]; int pf = 0, pc = 1; step[0] = 0; cx[0] = -1; cy[0] = -1; status[0] = pstatus; father[0] = 0; 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; father[pc] = pf; cx[pc] = i; cy[pc] = j; if (check(status[pc])) { output(step[pf] + 1); cout << endl; output_detail(pc, status, cx, cy, father); 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; } |
一不小心看到的,顺便膜拜下
@汪小益:你在做 POJ 吗?