#3037. 解救huhe(BFS+位运算)

解救huhe(BFS+位运算)

Background

BFS+位运算

Description

很久以前,魔法世界有一些“疯狂”魔法师就称:时空是破碎的,我们的世界,包括向和时间,并不是无股可分的,而是内无数的微小“积木”搭建而成。换言之,空问不是连续的,而是一粒一粒的组成,时间也不是一条连续流淌的长河,而是如时钟的滴答声一般,“滴答”次,就大约是一个普朗克时间:10^(-43)秒。虽然该理论正确与否至今无法验证,却有魔法师受此启发,创造了一种空前绝后的魔法一“时空陷”。

现在,因为某人的疏忽,而导致huhe在追踪修罗王的过程中,误中了“修罗”王设下的“时空陷”魔法。解救的方法如图 所示,有4X4的正方形,每个格子里的棋子要么是黑色,要么是白色,当把一个格子里的棋子颜色改变(黑->白或者白->黑)时,其周围上下左右(如果存在的话)的格子里的棋子颜色也被反转,除非将正方形里的所有棋子全部变为纯白或者纯黑,才可以将huhe解救出来,问至少反转几个棋子可以使 4X4 的正方形变为纯白或者纯黑?

image

Format

Input

4行4列的棋盘描述,其中 b代表黑色,w 代表白色

Output

一个整数即翻转次数。若无法完成,则输出“Impossible”

Samples

bwwb
bbwb
bwwb
bwww

4