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

    有一个有趣的手机游戏,有n*n个正方形的小按钮,有的按钮是黄色,有的按钮是白色。玩家的任务是通过点击按钮,让所有按钮都变成黄色,点按钮的次数越少,得分越高。
    但是按钮有个奇怪的特点,当你点击了坐标为(x,y)的按钮后,坐标为(x,y),(x+1,y),(x-1,y),(x,y-1),(x,y+1)的五个按钮会同时改变自身的颜色,是白色的变成黄色,黄色的变成白色。完成游戏最少需要点击多少次按钮呢?请找出答案。

    输入格式

    第一行,一个整数n,表示有n*n个按钮。(1<=n<=40)
    接下来是一个由小写字母'y'和字符'w'构成的n*n的矩阵,描述了游戏开始时的情景。'y'表示该按钮式黄色,'w'表示该按钮式白色。

    输出格式

    如果能够完成游戏,输出一个整数,表示所需最小点击次数。
    如果无法完成游戏,输出"inf"

    样例输入

    样例输入1:
    2
    yw
    ww

    样例输入2:

    5
    wwwww
    wwwww
    wwwww
    wwwww
    wwwww

    样例输出

    样例输出1:
    1

    样例输出2:
    15


    来源  改编自poj 1681