#include #include #include using namespace std; #define INFTY INT_MAX #define NSTATE (1<<16) #define FINALON ((1<<16)-1) #define FINALOFF 0 int toStateInt( bool S[6][6] ) { int result = 0; for ( int i = 1; i <= 4; i++ ) for ( int j = 1; j <= 4; j++ ) if ( S[i][j] ) result = (result << 1) | 1; else result = (result << 1) | 0; return result; } int makeNextState( bool S[6][6], int r, int c ) { const static int dr[] = {0, -1, +1, 0, 0}; const static int dc[] = {0, 0, 0, -1, +1}; for ( int i = 0; i < 5; i++ ) S[r+dr[i]][c+dc[i]] = !S[r+dr[i]][c+dc[i]]; int result = toStateInt(S); for ( int i = 0; i < 5; i++ ) S[r+dr[i]][c+dc[i]] = !S[r+dr[i]][c+dc[i]]; return result; } void toIntState( bool S[6][6], int sid ) { for ( int i = 4; i >= 1; i-- ) for ( int j = 4; j >= 1; j-- ) S[i][j] = ((sid & 1) == 1), sid >>= 1; } int compute( int init ) { queue Q; bool visited[NSTATE]; for ( int i = 0; i < NSTATE; i++ ) visited[i] = false; visited[init] = true; Q.push(init); for ( int d = 0; !Q.empty(); d++ ) for ( int size = Q.size(); size > 0; size-- ) { const int state = Q.front(); Q.pop(); if ( state == FINALON ) return d; if ( state == FINALOFF ) return d; bool S[6][6]; toIntState(S, state); for ( int i = 1; i <= 4; i++ ) for ( int j = 1; j <= 4; j++ ) { const int next = makeNextState(S, i, j); if ( visited[next] ) continue; visited[next] = true; Q.push(next); } } return INFTY; } int main() { char ch; while ( true ) { bool S[6][6]; for ( int i = 1; i <= 4; i++ ) for ( int j = 1; j <= 4; j++ ) { if ( !(cin >> ch) ) return 0; S[i][j] = (ch == 'b')? true : false; } const int initState = toStateInt(S); const int result = compute(initState); if ( result == INFTY ) cout << "Impossible" << endl; else cout << result << endl; } return 0; }