1712: 翻转游戏
内存限制:256 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:7
解决:4
题目描述
翻转游戏是在一个4格×4格的长方形上进行的,在长方形的16个格上每个格子都放着一个双面的物件。每个物件的两个面,一面是白色,另一面是黑色,每个物件要么白色朝上,要么黑色朝上,每一轮你只能翻3至5个物件,从而由黑到白地改变这些物件上面的颜色,反之亦然。每一轮被选择翻转的物件遵循以下规则:
1. 从16个物件中任选一个。
2. 翻转所选择的物件的同时,所有与它相邻的左方物件、右方物件、上方物件、下方物件(如果有的话),都要跟着翻转。
以下为例:
bwbw
wwww
bbwb
bwwb
这里“b”表示该格子放的物件黑色面朝上、“w”表示该格子放的物件白色朝上。如果我们选择翻转第三行的第一个物件(如下图所示),那么格子状态将为:
bwww
wwwb
wwwb
游戏的目标是翻转到所有的物件白色朝上或黑色朝上。你的任务就是写一个程序求最少的翻转次数来实现这一目标
输入
包含4行,每行4个字符,每个字符“w”或“b”表示游戏开始时格子上物件的状态。
输出
仅一个整数,即从给定状态到实现这一任务的最少翻转次数。如果给定的状态已经实现了目标就输出0,如果不可能实现目标就输出“Impossible”。
样例输入 复制
bwwb
bbwb
bwwb
bwww
样例输出 复制
4