TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • 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,表示有nn个按钮。(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