2 shunfurh shunfurh 于 2017.09.09 23:37 提问

Flip Game

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 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).

This problem contains multiple test cases!

The first line of a multiple input is an integer N, then a blank line followed by N input blocks. Each input block is in the format indicated in the problem description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between output blocks.

Sample Input

2

bwbw
wwww
bbwb
bwwb

bwwb
bbwb
bwwb
bwww

Sample Output

Impossible

4

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.26 16:34
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Flip Game(状态压缩+BFS)
Link:http://poj.org/problem?id=1753 Flip Game Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 32393   Accepted: 14147 Description Flip game
poj 1753 Flip Game(枚举,bfs)(简单)
poj 1753 Flip Game题目http://poj.org/problem?id=1753 给你一个4*4的棋盘,每个棋子非黑即白,翻一个棋子会带动它上下左右的棋子也翻过来,问至少多少次可以使棋盘全黑或者全白。思路只有16个棋子,所以用2进制状态压缩,用^=进行翻棋子的操作,当然要判断一下在不在棋盘内,接着就是枚举每个状态16个棋子翻的状态,进行判断,如果超了16步就是不可能了,因为
[LeetCode 293] Flip Game
You are playing the following Flip Game with your friend: Given a string that contains only these two characters:+ and -, you and your friend take turns to flip two consecutive "++" into "--". The g
LeetCode 293. Flip Game(反转游戏)
原题网址:https://leetcode.com/problems/flip-game/ You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take
[LeetCode294] Flip Game II
Flip Game II -- LeetCode 294 You are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The g
poj 1753 Flip Game(广搜)
poj 1753 Flip Game(广搜)
zoj 2050 -Flip Game题解
Flip Game Time Limit: 2 Seconds      Memory Limit: 65536 KB 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 wh
[LeetCode293] Flip Game
EasyYou are playing the following Flip Game with your friend: Given a string that contains only these two characters: + and -, you and your friend take turns to flip two consecutive "++" into "--". The
poj1753Flip Game之 广搜解法+暴搜解法
题意:每次翻一个棋子会带动周围棋子翻面,问需要的最小翻棋次数使得棋盘颜色一致。 分析:棋盘上有16个棋子,分别对应二进制数的16-1位,用1表示black或white,这样一个整数value就可以表示一种棋盘状态。 每次翻棋可以用异或^进行,然后在value的基础上进行搜索。 /*输入方式一*/ // int k = 0; // for (int i = 0; i < 4; ++i){ //
POJ 1753 Flip Game (DFS 太暴力了!)
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 p