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 釋出。