编程题＃1： 画家问题

编程题＃1： 画家问题

来源: POJ (Coursera声明：在POJ上完成的习题将不会计入Coursera的最后成绩。)

注意： 总时间限制: 1000ms 内存限制: 65536kB

描述

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

输入

第一行是个整数t(1≤t ≤20)，表示要测试的案例数。然后是t个案例。每个案例的首行是一个整数n (1≤n ≤15)，表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖，“y”表示黄砖。

输出

每个案例输出一行。如果Bob能够将所有的砖都涂成黄色，则输出最少需要涂画的砖数，否则输出“inf”。

样例输入

2
3
yyy
yyy
yyy
5
wwwww
wwwww
wwwww
wwwww
wwwww

样例输出

0
15 

代码

需要说明的是，本代码稍微修改适配POJ的问题后在POJ能AC，但是在Coursera的作业界面会编译错误（目前还未找到原因）。

// 基于视频中老师提供的方法

#include <iostream>
#include <math.h>

using namespace std;

// 通过第一行的原始情况和涂画情况来递推后面逐行的图画情况
bool guess(int n , int *p1 , int *p2) {
    int c,r;
    for (r=1;r<n;r++) {
        for (c=1;c<(n+1);c++)
            p2[(r+1)*(n+2)+c]=(p1[r*(n+2)+c]+p2[r*(n+2)+c]+p2[(r-1)*(n+2)+c]+p2[r*(n+2)+c-1]+p2[r*(n+2)+c+1])%2;
    }
    for(c=1;c<(n+1);c++) {
        if ((p2[n*(n+2)+c-1]+p2[n*(n+2)+c]+p2[n*(n+2)+c+1]+p2[(n-1)*(n+2)+c])%2!=p1[n*(n+2)+c])
            return false;
    }
    return true;
}

// 对第一行的图画情况进行枚举，判断符合要求的结果并统计涂画的块数
int enumerate(int n,int *p1,int *p2){
    int c;
    int mindraw=226;
    int sum=0;
    for (c=1;c<(n+1);c++)
        p2[n+2+c]=0;
    int i,r;
    for (i=0;i<pow(2,n);i++) {
        if (guess(n,p1,p2)==true) {
            for (r=1;r<(n+1);r++) {
                for (c=1;c<(n+1);c++) {
                    sum=sum+p2[r*(n+2)+c];
                }
            }
            if (sum<mindraw) mindraw=sum;
        }
        p2[n+2+1]++;
        c=1;
        while (p2[n+2+c]>1) {
            p2[n+2+c]=0;
            c++;
            p2[n+2+c]++;
        }
    }
    return mindraw;
}

int main()
{
    int t;
    cin >> t;
    int results[t];
    int i;
    for (i=0;i<t;i++) {
        int n;
        cin >> n;
        int r,c;
        char init[n+1][n+2];
        int draw[n+1][n+2];
        int init2[n+1][n+2]={0};
        for(r=0;r<n+1;r++)
            draw[r][0]=draw[r][n+1]=0;
        for(c=1;c<n+1;c++)
            draw[0][c]=0;
        for (r=1;r<(n+1);r++) {
            for (c=1;c<(n+1);c++) {
                cin >> init[r][c];
                if (init[r][c]=='w')
                    init2[r][c]=1;
            }
        }
        results[i]=enumerate(n,&init2[0][0],&draw[0][0]);
    }
    for (i=0;i<t;i++) {
        if (results[i]==226) cout << "inf" <<endl;
        else cout << results[i] <<endl;
    }
    return 0;
}

POJ链接以及AC的代码。

#include <iostream>
#include <math.h>

using namespace std;

bool guess(int n , int *p1 , int *p2) {
    int c,r;
    for (r=1;r<n;r++) {
        for (c=1;c<(n+1);c++)
            p2[(r+1)*(n+2)+c]=(p1[r*(n+2)+c]+p2[r*(n+2)+c]+p2[(r-1)*(n+2)+c]+p2[r*(n+2)+c-1]+p2[r*(n+2)+c+1])%2;
    }
    for(c=1;c<(n+1);c++) {
        if ((p2[n*(n+2)+c-1]+p2[n*(n+2)+c]+p2[n*(n+2)+c+1]+p2[(n-1)*(n+2)+c])%2!=p1[n*(n+2)+c])
            return false;
    }
    return true;
}

int enumerate(int n,int *p1,int *p2){
    int c;
    int mindraw=226;
    int sum=0;
    for (c=1;c<(n+1);c++)
        p2[n+2+c]=0;
    for (int i=0;i<pow(2,n);i++) {
        if (guess(n,p1,p2)==true) {
            for (int r=1;r<(n+1);r++) {
                for (c=1;c<(n+1);c++) {
                    sum=sum+p2[r*(n+2)+c];
                }
            }
            if (sum<mindraw) mindraw=sum;
        }
        p2[n+2+1]++;
        c=1;
        while (p2[n+2+c]>1) {
            p2[n+2+c]=0;
            c++;
            p2[n+2+c]++;
        }
    }
    return mindraw;
}

int main()
{
        int result;
        int n;
        cin >> n;
        int r,c;
        char init[n+1][n+2];
        int draw[n+1][n+2];
        int init2[n+1][n+2]={0};
        for(r=0;r<n+1;r++)
            draw[r][0]=draw[r][n+1]=0;
        for(c=1;c<n+1;c++)
            draw[0][c]=0;
        for (r=1;r<(n+1);r++) {
            for (c=1;c<(n+1);c++) {
                cin >> init[r][c];
                if (init[r][c]=='w')
                    init2[r][c]=1;
            }
        }
        result=enumerate(n,&init2[0][0],&draw[0][0]);

        if (result==226) cout << "inf" <<endl;
        else cout << result <<endl;

    return 0;
}