Problem1270--翻转游戏 turn

1270: 翻转游戏 turn

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MiB

Description

翻转游戏是这样玩的:有一张4*4的棋盘,在16个位置上每个位置放着一个棋子,棋子一面是黑色,另一面是白色,棋子要不白色面朝上,要不黑色面朝上。游 戏的走法如下:每一步先选择一个位置,然后把该位置和上,下,左,右相邻位置上的棋子翻转(白->黑,黑->白)。我们用w表示棋子白色面朝 上,b表示黑色面朝上。
例如:考虑如下棋盘状态:
bwbw
wwww
bbwb
bwwb
当我们选择第三行,第一列的位置翻转时,棋盘变化为
bwbw
bwww
wwwb
wwwb
翻转过程如图所示:


游戏的目的是用最少的步数把全部棋子变为白色向上或黑色向上。

Input

输入:接下来每4行描叙了一个棋盘的初始状态

Output

输出:输出最少的翻转次数,如果无法翻转成目标状态,则输出Impossible。

Sample Input

输入	输出
bwbw     Impossible
wwww
bbwb
bwwb	Impossible

输入	输出
bwwb     4
bbwb
bwwb
bwww 

Sample Output

 

Hint

位操作

Source/Category