画家问题

http://cxsjsxmooc.openjudge.cn/test/Y/

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using std::cin;
using std::cout;
using std::endl;
int map[20][20];//草稿
int copy[20][20];//原始记录
int line[20];//第一行
char col[20];//输入缓冲区
int n;
int min;
int count;
void draw(int x,int y){//画画并且增加次数
    map[x][y]=!map[x][y];
    map[x-1][y]=!map[x-1][y];
    map[x+1][y]=!map[x+1][y];
    map[x][y-1]=!map[x][y-1];
    map[x][y+1]=!map[x][y+1];
    count++;
}
bool guess(){
    //从第二行开始 判断每个点上边的点是否为黄色 如果不是黄色 则涂该点
    for(int i=2; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(map[i-1][j] == 0)
                draw(i,j);


    //判断最后一行是否都为黄色 如果是则记录次数 否则提交失败
    for(int k=1; k<=n; k++)
        if(map[n][k] != 1)
            return false;
    if(count < min)
        min = count;
    return true;
}
void getLine(int k){
    //二进制枚举第一行
    int j=n;
    while(j>0){
        line[j]=k%2;
        k/=2;
        j--;
    }
}
int main(){
    int w;
    cin>>w;
    while(w--){
        cin>>n;
        min=n*n+1;
        for (int i = 1; i <=n; ++i) {
            scanf("%s",col);
            //一行一行扫描
            for (int j = 1; j <=n ; ++j) {
                if(col[j-1]=='w'){
                    copy[i][j]=0;
                }
                else{
                    copy[i][j]=1;
                }
            }
        }
        //开始枚举
        for (int k = 0; k <pow(2,n) ; ++k) {
            count=0;
            memcpy(map,copy, sizeof(copy));
            getLine(k);
            //枚举第一行
            for (int i = 1; i <=n ; ++i) {
                if(line[i]==1){
                    draw(1,i);
                }
            }
            guess();
        }
        if(min!=n*n+1){
            cout<<min<<endl;
        }
        else{
            cout<<"inf"<<endl;
        }
    }
    return 0;
}