题目描述
翻转游戏是这样玩的:
有一张4*4的棋盘,在16个位置上每个位置放着一个棋子,棋子一面是黑色,另一面是白色,棋子或者白色面朝上,或者黑色面朝上。游戏的走法如下:每一步先选择一个位置,然后把该位置和上,下,左,右(不越界)相邻位置上的棋子翻转(白->黑,黑->白)。我们用w表示棋子白色面朝上,b表示黑色面朝上。
例如:考虑如下棋盘状态:
bwbw
wwww
bbwb
bwwb
当我们选择第三行,第一列的位置翻转时,棋盘变化为:
bwbw
bwww
wwwb
wwwb
游戏的目的是用最少的步数把全部棋子变为白色向上或黑色向上。
时限:1s。
输入格式
4行由b和w组成的字符串描述的一个棋盘的初始状态。
输出格式
一个测试数据输出一行,为所需要的最少的翻转次数,如果无法翻转成目标状态,则输出’impossible’(小写,没有引号)。
样例输入
样例输出