POJ 1681 Painter's Problem （高斯消元）

Description

Input

The first line contains a single integer t (1 <= t <= 20) that indicates the number of test cases. Then follow the t cases. Each test case begins with a line contains an integer n (1 <= n <= 15), representing the size of wall. The next n lines represent the original wall. Each line contains n characters. The j-th character of the i-th line figures out the color of brick at position (i, j). We use a ‘w’ to express a white brick while a ‘y’ to express a yellow brick.

Output

For each case, output a line contains the minimum number of bricks Bob should paint. If Bob can’t paint all the bricks yellow, print ‘inf’.

Sample Input

23yyyyyyyyy5Output

015

题意

给出一个 n×n

思路

考虑有 n×n 个多项式，每一个多项式涉及到上下左右以及自身的五个变量，其结果为 ​​1​​ 。

然后代入高斯消元求出方程组的解，若唯一解，统计 ​​1​​​ 的个数；若有无穷多个解，枚举所有的自由变元找出最优解；若无解输出 ​​inf​​ 。

AC 代码

#include#include#include#include#include#include#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。