TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P1987
  • Problem
  • P1987【高斯消元】手机游戏
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Description

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

    Input Format

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

    Output Format

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

    Sample Input

    样例输入1:
    2
    yw
    ww

    样例输入2:

    5
    wwwww
    wwwww
    wwwww
    wwwww
    wwwww

    Sample Output

    样例输出1:
    1

    样例输出2:
    15


    Source  改编自poj 1681