题目描述

翻转游戏在一个 4x4 的矩形棋盘上进行，棋盘上的每个方格放置了一个双面棋子，一面是白色（w），另一面是黑色（b）。初始状态下，每个棋子可能正面朝上的是黑色或白色。

每一轮，你可以翻转 3 到 5 个棋子，即改变它们的颜色（黑变白，白变黑）。翻转的棋子选择遵循以下规则：

1. 选择任意一个棋子（共 16 个）。
2. 翻转该棋子及其上下左右相邻的棋子（如果存在）。

示例

初始棋盘状态：

b w b w  
w w w w  
b b w b  
b w w b  

如果选择第 3 行的第 1 个棋子（b），则翻转该棋子及其相邻的棋子（右侧的 b 和下方的 b），棋盘变为：

b w b w  
b w w w  
w w w b  
w w w b  

游戏目标

通过最少的轮次，使得棋盘上的所有棋子 全部变为白色（w）或全部变为黑色（b）。

输入

输入包含 4 行，每行 4 个字符 w 或 b，表示初始棋盘状态。

输出

• 如果能达到目标，输出 最少需要的轮次。
• 如果初始状态已经满足目标，输出 0。
• 如果无法达到目标，输出 Impossible。

输入样例 1

b w w b  
b b w b  
b w w b  
b w w w  

输出样例 1

4

来源

Northeastern Europe 2000