题目描述
翻转游戏在一个正方形的4x4场地上进行,在其16个方格中分别放置双面棋子。每个棋子的一面是白色,另一面是黑色,每件都是黑色或白色朝上。每一轮你翻转3至5件,从而将其上侧的颜色从黑色改为白色,反之亦然。根据以下规则,每轮选择要翻转的棋子:
选择16个中的任何一个。
将所选棋子以及所有相邻棋子(包括上下左右)翻转。
例子:
bwbw
wwww
bbwb
bwwb
这里“b”表示黑色面朝上的棋子,“w”表示白色面朝上的棋子。如果我们选择从第3行翻转第1个,那么将变为:
bwbw
bwww
wwwb
wwwb
游戏的目标是翻转所有棋子白色面朝上或所有棋子黑色朝上。你将编写一个程序来搜索实现此目标所需的最少轮数。
输入描述
多组输入(不超过10组),输入由4行组成,每行4个字符“w”或“b”。
输出描述
每组数据输出一行,包含一个整数或者字符串,整数代表从给定位置实现游戏目标所需的最小轮数,如果无法实现目标,则输出“Impossible”。
样例输入
bwwb
bbwb
bwwb
bwww
样例输出
4
提示