#include <iostream>
#include <queue>
using namespace std;
bool g[4][4];
int binary[16]= 
{ 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768 };
bool visited[65538];
int change( bool gg[4][4] )
{
int num= 0;
int t= 15;
for ( int i= 0; i< 4; ++i )
for ( int j= 0; j< 4; ++j )
{
if ( gg[i][j] ) num+= binary[t];
t--;
}
return num;
}
void recover( int data, bool temp[4][4] )
{
int re[16];
int t= 15;
memset( re, 0, sizeof(re) );
while ( data!= 0 )
{
re[t]= ( data% 2 );
data/= 2;
t-- ;
}
t= 0;
for ( int i= 0; i< 4; ++i )
for ( int j= 0; j< 4; ++j )
{
temp[i][j]= ( re[t]== 1 );
t++;
}
}
struct Node
{
int value;
int steps;
Node()
{}
Node( int a, int b )
:value(a), steps(b)
{}
};
void copy( bool b1[4][4], bool b2[4][4] )
{
for ( int i= 0; i< 4; ++i )
for ( int j= 0; j< 4; ++j )
b2[i][j]= b1[i][j];
}
void print( bool b[4][4] )
{
for ( int i= 0; i< 4; ++i )
{
for ( int j= 0; j< 4; ++j )
cout << b[i][j] << ' ';
cout << endl;
}
}
int main()
{
for ( int i= 0; i< 4; ++i )
{
for ( int j= 0; j< 4; ++j )
{
char ch;
scanf("%c",&ch);
g[i][j]= ( ch== 'b' );
}
getchar();
}
memset( visited, false, sizeof(visited) );
queue<Node> q;
q.push( Node( change(g), 0 ) );
visited[ change(g) ]= true;
bool ans= false;
while ( !q.empty() )
{
bool temp[4][4];
Node t= q.front();
q.pop();
if ( t.value== 0 || t.value== 65535 )
{
printf("%d", t.steps );
ans= true;
break;
}
recover( t.value, temp );
for ( int i= 0; i< 4; ++i )
for ( int j= 0; j< 4; ++j )
{
bool tt[4][4];
copy( temp, tt );
tt[i][j]= !tt[i][j];
if ( i- 1>= 0 ) tt[i-1][j]= !tt[i-1][j];
if ( i+ 1< 4 ) tt[i+1][j]= !tt[i+1][j];
if ( j- 1>= 0 ) tt[i][j-1]= !tt[i][j-1];
if ( j+ 1< 4 ) tt[i][j+1]= !tt[i][j+1];
int curr= change( tt );
if ( !visited[curr] )
{
q.push( Node( curr, t.steps+ 1) );
visited[curr]= true;
}
}
}
if ( !ans ) printf("Impossible");
return 0;
}
posted on 2008-11-06 12:40
Darren 阅读(354)
评论(0) 编辑 收藏 引用