POJ-1753 transmission

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;
}