POJ1753 solution
This probem is named Flip Game that I’ve ever play in my childrenhood. It’s a very difficult game for me until last night. Maybe you have similar feeling.OK, cut the crap and look at the following solution I use.
First, we can define one kind of layout of the chessboard as a 16-bit number, so there are 65535 kinds of the layout. Absolutely, we can see the character ‘b’ as 1, and ‘w’ as 0. So the layout provided by the subject is 1001110110011000 in binary.
Second, according to the following role:
1. Choose any one of the 16 pieces.
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
After one round the state will change to another which is never appeared(if not, we should not step the position, otherwith we may recycle all the time).
OK, now. It’s obviously that we should use the BPS to find the answer and construct a tree using the number resulted from the layout of the field.
The number 1001110110011000 should be the root and he has 16 children corresponding to 16 kinds of layout after one round. Analogously, each of the children has 16 children, too. OK, I know it will be a very huge 16-tree, so in order to minimize the tree, we should not insert the node which is already appeared into the tree.
Now, Let’s have a look at my code.
/********************************************************************
created: 2011/09/14
created: 14:9:2011 10:04
filename: e:\MyCode\ACM\POJ\POJ1753\main.cpp
file path: e:\MyCode\ACM\POJ\POJ1753
file base: main
file ext: cpp
author: Michael
purpose: Flip Game
problem prom: http://poj.org/problem?id=1753
offline decription: e:\MyCode\ACM\POJ\POJ1753\Decription.txt
*********************************************************************/
#include <iostream>
#include <deque>
#include <stdio.h>
#include <fstream>
#include <bitset>
using namespace std;
typedef struct StateNode
{
bitset<16> btValue;//the value of state in the style of bitset
int iStep;//the number of round from the original state to this one;
}StateNode;
bool iExitSet[65535];// referance to whether the state has been already searched;
int FindSolution( const StateNode & snOriginal)
{
memset(iExitSet, 0, 65535);
if ( snOriginal.btValue.to_ulong() == 0 || snOriginal.btValue.to_ulong() == 65535)
{
return 0;
}
deque< StateNode > deqStateNode;
deqStateNode.push_back( snOriginal );
iExitSet[snOriginal.btValue.to_ulong()] = 1;
deque< StateNode >::iterator itr;
int iLeft, iRight, iTop, iBottom;
while ( !deqStateNode.empty() )//find the node with value 0 or 65535 until the deque is empty
{
const StateNode &nodeFront = deqStateNode.front();
for ( int i = 0; i < 16; i++)
{
StateNode node = nodeFront;
iLeft = i - 1;
iRight = i + 1;
iTop = i - 4;
iBottom = i + 4;
if ( i % 4 - 1>= 0 )
{
node.btValue.test(iLeft) ? node.btValue.reset(iLeft) : node.btValue.set(iLeft);
}
if ( i % 4 + 1 < 4 )
{
node.btValue.test(iRight) ? node.btValue.reset(iRight) : node.btValue.set(iRight);
}
if ( i /4 + 1 < 4 )
{
node.btValue.test(iBottom) ? node.btValue.reset(iBottom) : node.btValue.set(iBottom);
}
if ( i / 4 - 1 >= 0 )
{
node.btValue.test(iTop) ? node.btValue.reset(iTop) : node.btValue.set(iTop);
}
node.btValue.test(i) ? node.btValue.reset(i) : node.btValue.set(i);
unsigned long ulValue = node.btValue.to_ulong();
if ( ulValue == 0 || ulValue == 65535)
{
return nodeFront.iStep + 1;
}
if (iExitSet[ulValue] == false)
{
iExitSet[ulValue] = true;
node.iStep = nodeFront.iStep + 1;
deqStateNode.push_back(node);
}
}
deqStateNode.pop_front();
}
return -1;
}
int main()
{
freopen("data.txt", "r", stdin);//redefine the standard input stream to the file called "data.txt"
//input the original state
// char cTemp;
// for ( int i = 0; i < 16; i++ )
// {
// cin>>cTemp;
// if ( cTemp == 'b' )
// {
// snOriginal.btValue.set(i);
// }
// else
// {
// snOriginal.btValue.reset(i);
// }
// }
ofstream ofile;
ofile.open("result.txt", ios_base::out);
for (int i = 0; i < 65535; i++)
{
StateNode snOriginal;//the original node provided by the problem and the initialize the variable.
snOriginal.btValue = bitset<16>(i);
snOriginal.iStep = 0;
int ret = FindSolution(snOriginal);
ofile<< ret << ",";
if( -1 == ret)
{
printf("Impossible");
}
else
printf("%d", ret);
}
ofile.close();
return 0;
}