POJ1681 Painter's Problem

总时间限制: 5000ms 内存限制: 65536kB

描述

There is a square wall which is made of n*n small square bricks. Some bricks are white while some bricks are yellow. Bob is a painter and he wants to paint all the bricks yellow. But there is something wrong with Bob's brush. Once he uses this brush to paint brick (i, j), the bricks at (i, j), (i-1, j), (i+1, j), (i, j-1) and (i, j+1) all change their color. Your task is to find the minimum number of bricks Bob should paint in order to make all the bricks yellow.

输入

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.

输出

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'.

样例输入

2
3
yyy
yyy
yyy
5
wwwww
wwwww
wwwww
wwwww
wwwww

样例输出

0
15

解题思路

和熄灯问题完全一样，只不过稍微做了一些变形，需要得到最小的操作步数。

解题代码

#include <iostream>
using namespace std;
int puzzle[16][17], press[16][17]; //因为最大边长是15，而行要增加第一行，列要增加最左右两列，来统一press计算公式
int n;

int guess(int min)//检查每一个第一行确定的press矩阵是否满足要求，并比较最小值
{
    int c, r, step = 0; //step记录操作数
    for (r = 1; r < n; r++)
    {
        for (c = 1; c <= n; c++)
        {
            press[r + 1][c] = (puzzle[r][c] + press[r][c] + press[r][c - 1]
                + press[r - 1][c] + press[r][c + 1]) % 2;  //计算下一行的press值

            if (press[r + 1][c]) {//如果下一行的该元素确定了需要操作的话
                step++;
                if (min >= 0 && step > min) {//已不可能是最小涂画数的话就没必要再计算
                    return -1;
                }
            }
        }
    }

    for (c = 1; c <= n; c++)//检查最后一行是否满足要求，不满足就退出读入下一个press
    {
        if ((press[n][c - 1] + press[n][c] + press[n][c + 1] + press[n - 1][c]) % 2
            != puzzle[n][c])
        {
            return -1;
        }
    }

    for (c = 1; c <= n; c++)//总操作数需加上第一行的操作数
    {
        if (press[1][c])
        {
            step++;
        }
    }
    return step;
}

int enumerate()//迭代出每一个press矩阵第一行的状态
{
    int min = -1;
    int c;

    for (c = 1; c < n + 2; c++)//press第一行清零，有效的就是1到n+1,n+1是判断枚举结束的位，puzzle不用清零的，因为每次就用那么多
    {
        press[1][c] = 0;
    }

    int temp = -1;

    while (press[1][n + 1] < 1)//判断枚举结束
    {
        temp = guess(min);
        if (temp >= 0)//更新最小操作数
        {
            if ((min == -1) || (temp < min))
            {
                min = temp;
            }
        }

        press[1][1]++;
        c = 1; //每次二进制的第一行都会从第一位开始加值
        
        while (press[1][c] > 1)//需要进位且未达到最后一位（n+1位)
        {
            press[1][c] = 0;
            c++;
            press[1][c]++;
        }
    }
    return min;
}

int main()
{
    int cases;
    cin >> cases;
    while (cases--)
    {
        cin >> n;
        int r, c;
        for (r = 0; r <= n; r++)//初始化最左列与最右列
        {
            puzzle[r][0] = puzzle[r][n + 1] = 0;
        }
        for (c = 1; c < n + 2; c++)//初始化第0行
        {
            puzzle[0][c] = 0;
        }
        char ch;
        for (r = 1; r <= n; r++) { //读入一开始的puzzle矩阵
            for (c = 1; c <= n; c++) {
                cin >> ch;
                puzzle[r][c] = ch == 'w' ? 1 : 0;
            }
        }
        int result = enumerate(); //如果成功就返回操作数
        if (result >= 0)
        {
            cout << result << endl;
        }
        else
        {
            cout << "inf" << endl;
        }
    }
    return 0;
}