Flip Game
InterviewTime limit1sMemory limit128 MB
Find the minimum number of flips to turn all 16 pieces white or all black, where each move flips a chosen cell and its orthogonal neighbors.
- Level
Medium6 of 10
- Topics
- Brute force, Bit manipulation, Backtracking, Implementation
- Solved
- No attempts yet
Problem
Flip game is played on a 4×4 board that has a two-sided piece on each of its 16 squares. One side of every piece is white and the other side is black, and each piece starts lying either its black or its white side up.
On every round you flip between 3 and 5 pieces, changing the color of the upper side of each flipped piece from black to white or from white to black. The pieces to flip are chosen each round according to the following rules:
- Choose any one of the 16 pieces.
- Flip the chosen piece and every piece adjacent to it on the left, right, top, and bottom (whenever such a piece exists).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here b denotes a piece lying black side up and w denotes a piece lying white side up. If we choose to flip the 1st piece in the 3rd row (the choice shown in the picture), the board becomes:
bwbw
bwww
wwwb
wwwb
The goal of the game is to make every piece lie white side up, or every piece lie black side up. Write a program that finds the minimum number of rounds needed to reach that goal from the given position.
Input
Four lines are given; each line describes one row of the board as 4 characters, each either 'w' or 'b'.
Output
Output a single integer: the minimum number of rounds needed to reach the goal from the given position. If the goal is already met, output 0. If the goal cannot be reached, output the word "Impossible" (without the quotes).