TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2222
  • Problem
  • P2222【位运算或高斯消元】开关游戏
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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


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

    Input Format

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

    Output Format

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

    Sample Input

    bwwb
    bbwb
    bwwb
    bwww

    Sample Output

    4


    Source  Northeastern Europe 2000