TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2222
  • 题目
  • P2222【位运算或高斯消元】开关游戏
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    在4x4的游戏棋盘上有16个方格,每个方格是一个开关,按一下点亮当前方格,再按以下就关闭当前方格。但是,当你按下当前方格时,它的上下左右四个方格同时会受到影响,原来点亮的会被关闭,原来关闭的会被点亮。


    游戏的目标是使得16个格子全部点亮或者全部熄灭,你的任务是找出最少的操作步数字。

    输入格式

    一个4x4的矩阵,"w"表示处于点亮状态,"b"表示处于关闭状态

    输出格式

    一个整数,表示最小步数,如果无解,输出“Impossible”

    样例输入

    bwwb
    bbwb
    bwwb
    bwww

    样例输出

    4


    来源  Northeastern Europe 2000