POJ 2965：非算法優化的重要：時間直減 50%！

/*
 *      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;
}