/ Vijos / 题库 /

画家问题

画家问题

时间限制:1秒  内存限制:256M


【问题描述】

  有一个正方形的墙,由 \(N×N\) 个正方形的砖组成,其中一些砖是白色的(用字母'w'表示),另外一些砖是黄色的(用字母'y'表示)。小H是个画家,想把全部的砖都涂成黄色。但他的画笔不好使,当他用画笔涂画第 \((i,j)\) 个位置的砖时,位置 \((i-1,j)、(i+1,j)、(i,j-1)、(i,j+1)\) 上的砖都会改变颜色。请你帮助小H计算出最少需要涂画多少块砖,才能使所有砖的颜色都变成黄色。
    说明

【输入格式】

  第一行是一个整数 \(N\),表示墙的大小。接下来的 \(N\) 行表示墙的初始状态。每一行包含 \(N\) 个字符。第 \(i\) 行的第 \(j\) 个字符表示位于位置 \((i,j)\) 上的砖的颜色,“w”表示白砖,“y”表示黄砖。

【输出格式】

  一行,如果小H能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。

【输入输出样例】

 Input

5
wwwww
wwwww
wwwww
wwwww
wwwww

 Output

15

【数据限制】

  对于 \(100\%\) 的数据:\(1≤N≤30\)

【来源】

  Mr.he

信息

ID
2716
难度
9
分类
线性代数 | 高斯消元搜索 点击显示
标签
(无)
递交数
1
已通过
1
通过率
100%
被复制
1
上传者