POJ 1753 Flip Game 题解 | 宁心勉学，慎思笃行

今天我做了 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;
}

本文版权遵循 CC BY-NC-SA 4.0发布，转载需附带本文链接。

猜你喜欢