## Title Translation:

The flip game is played on a rectangular 4x4 field, with two pieces placed on each of its 16 squares. One side of each block is white, the other side is black, and each block faces up with a black or white side. Flip 3 to 5 pieces per round to change the color of the upper side from black to white and vice versa. Select the pieces to be flipped in each round according to the following rules:

Select any of the 16 pieces.

Flips the selected clip and all adjacent clips to the left, right, top, and bottom of the selected clip, if any.

## Consider the following locations as examples:

bwbw wwww bbwb bwwb

Here, "b" refers to the sheet with its black side facing upward, and "w" refers to the sheet with its white side facing upward. If we choose to flip the first block from the third row (as shown in the figure), the field will change to:

bwbw bwww wwwb wwwb

The goal of the game is to turn all the white faces up or all the black faces up. You will write a program that will search for the minimum number of rounds required to achieve this goal.

## Input item

The input includes 4 lines, each line contains 4 characters "w" or "b" respectively, indicating the location of the game field.

## Output

Write an integer to the output file - the minimum number of rounds required to reach the game goal from a given location. If the goal is reached initially, write 0. If it is Impossible to achieve the goal, write "Impossible" (without quotation marks).

## Sample input

bwwb bbwb bwwb bwww

## Sample output

4

## Idea:

Simple violence deep search, because the chessboard is not large (the main reason is that currently only this method is used). There are two situations for each chess piece, turning or not turning. If you turn, you should turn yourself and the four pieces up, down, left and right at the same time, and then turn back when you go back. When you keep comparing the chess board, you can get the minimum number of operations.

## Code:

#include <iostream> #include <algorithm> using namespace std; char chess[4][4],now[]={'w','b'}; //Chessboard, piece type int ans=1<<27; //ans initial value, set to a large number char revise(char c) //Flip { if(c==now[0]) return now[1]; else return now[0]; } bool in(int x,int y) //Judge whether the location is feasible~ { if(x>=0 && x<4 && y>=0 && y<4) return 1; return 0; } bool isOk(char chess[4][4]) //Judge whether the chessboard is uniform~ { for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(chess[i][j]!=chess[0][0]) return 0; return 1; } void op(int x,int y) //Operation: flip the current position and the pieces up, down, left and right { chess[x][y]=revise(chess[x][y]); //If it is within the boundary, the chess pieces will be flipped if(in(x+1,y)) chess[x+1][y]=revise(chess[x+1][y]); if(in(x-1,y)) chess[x-1][y]=revise(chess[x-1][y]); if(in(x,y-1)) chess[x][y-1]=revise(chess[x][y-1]); if(in(x,y+1)) chess[x][y+1]=revise(chess[x][y+1]); } void dfs(int x,int y,int k) //Position (x,y), number of operations k { if(isOk(chess)) //Uniform~ { ans=min(ans,k); //Minimum number of times return; } if(!in(x,y)) return; //Out of range, return int newy=(y+1)%4; //Get the coordinates of the next position (y = 0 12 3) int newx=x+(y+1)/4; //The value of X depends on whether y+1 is equal to 4. If y+1 is equal to 4, then x+1 dfs(newx,newy,k); op(x,y); dfs(newx,newy,k+1); op(x,y); //Backtracking } int main() { for(int i=0;i<4;i++) for(int j=0;j<4;j++) cin>>chess[i][j]; dfs(0,0,0); if(ans==1<<27) cout<<"Impossible"; else cout<<ans; return 0; }