网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[NOIP2010冲刺七]翻转游戏
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | flip.in | 输出文件 | flip.out |
【题目描述】
翻转游戏是在一个4格×4格的长方形上进行的,在长方形的16个格上每个格子都放着一个双面的物件。每个物件的两个面,一面是白色,另一面是黑色,每个物件要么白色朝上,要么黑色朝上,每一轮你只能翻3至5个物件,从而由黑到白的改变这些物件上面的颜色,反之亦然。每一轮被选择翻转的物件遵循以下规则:
1、从16个物件中任选一个。
2、翻转所选择的物件的同时,所有与它相邻的左方物件、右方物件、上方物件和下方物件(如果有的话),都要跟着翻转。
以下为例:
bwbw
bbwb
bwwb
这里"b"表示该格子放的物件黑色面朝上、"w"表示该格子放的物件白色朝上。如果我们选择翻转第三行的第一个物件,那么格子状态将变为:
bwbw
bwww
wwwb
wwwb
游戏的目标是翻转到所有的物件白色朝上或黑色朝上。你的任务就是写一个程序来求最
少的翻转次数来实现这一目标。
【输入格式】
输入文件flip.in包含4行,每行4个字符,每个字符"w" 或 "b"表示游戏开始时格子上物件的状态。
【输出格式】
输出文件flip.out仅一个整数,即从给定状态到实现这一任务的最少翻转次数。如果给定的状态就已经实现了目标就输出0,如果不可能实现目标就输出"Impossible"。
【样例输入】
bwwb bbwb bwwb bwww
【样例输出】
4【来源】
冲刺NOIP2010模拟试题与解析(七)(提高组复赛)