POJ-1753-Flip Game

Description

Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:

Choose any one of the 16 pieces.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).

Consider the following position as an example: bwbw wwww bbwb bwwb Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become: bwbw bwww wwwb wwwb The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

Input

The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.

Output

Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).

Sample Input

bwwb bbwb bwwb bwww

Sample Output

4 题意： 有一个4*4的棋盘,棋盘上有黑白格,每一次你可以翻其中的一个格子。一个格子(x,y)如果被翻,它相邻的前后左右四个格子（如果在棋盘上）也要翻转。现在给你一个初始的棋盘状态，问把这个棋盘翻转到全黑或全白的最少次数；若不能达到全黑或全白，输出Impossible。

思路：直接暴力枚举，首先要知道一个格子不管翻转多少次，翻转奇数次的结果总是一样的，偶数次的情况也相同，所以可以从第一个格子开始先枚举翻转一次的情况，然后是翻转两次，翻转三次，原先以为翻转次数最多到16次，就是每个格子都反转一次但是次序不一样。然而经过poj提交测试发现，最多只需要6次就可以把所有的情况都枚举完成，所以我猜想如果poj上的数据把所有的情况都包括的话，那么必定存在两个或多个虽然反转次数是不一样的但是结果却是一样的。其实直觉上很好理解，因为一共格子翻转次数实际上是只有0次和1次，因为翻转奇数次跟翻转1次的效果是一样的，同理0次跟偶数次一样，那么就有可能某些情况，虽然翻转次数不一样但是效果是一样的，所以才有最多翻转6次的答案。当然以上是我自己的猜测还没有实际的验证。

#include <stdio.h> char map[4][4]; void filp(int n)//反转函数 { int row = n / 4; int col = n % 4; map[row][col] = map[row][col] == 'w' ? 'b' : 'w'; if (row > 0) { map[row-1][col] = map[row-1][col] == 'w' ? 'b' : 'w'; } if (col < 3) { map[row][col+1] = map[row][col+1] == 'w' ? 'b' : 'w'; } if (row < 3) { map[row+1][col] = map[row+1][col] == 'w' ? 'b' : 'w'; } if (col > 0) { map[row][col-1] = map[row][col-1] == 'w' ? 'b' : 'w'; } } bool dfs(int n,int cnt) //n表示第几个格子（一共16个格子）cnt表示次数 { if (cnt == 0) { //递归出口 如果颜色一样就返回ture 不一样false int c = map[0][0]; for (int i = 0; i < 4; i++) { for (int j = 0; j < 4; j++) { if(c != map[i][j]) { return false; } } } return true; } for (int i = n; i < 16; i++) { //从第n块开始翻转，只翻转第n块之后的，翻转cnt次 filp(i); if(dfs(i + 1, cnt - 1)) { return true; } filp(i);//运行到这里说明上一个反转的组合不对，要还原成原来的样子 } return false; } int main() { for (int i = 0; i < 4; i++) { //输入 scanf("%s",map[i]); } bool flag = false; for (int i = 0; i <= 6; i++) { //i表示翻转次数，本来以为翻转的次数最大应该是16次，但是经过实验i<=6也可以过 if (dfs(0, i)) { printf("%d\n",i); flag = true; break; } } if (!flag) { printf("Impossible\n"); } return 0; }