Openjudge 画家问题

画家问题

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

输入
第一行是一个整数n (1≤n ≤15),表示墙的大小。接下来的n行表示墙的初始状态。每一行包含n个字符。第i行的第j个字符表示位于位置(i,j)上的砖的颜色。“w”表示白砖,“y”表示黄砖。
输出
一行,如果Bob能够将所有的砖都涂成黄色,则输出最少需要涂画的砖数,否则输出“inf”。
样例输入
5
wwwww
wwwww
wwwww
wwwww
wwwww
样例输出
15
来源
1681

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
int n,max_n=1e9;
bool array[16][16];
bool usearr[16][16];
bool press[16][16];
inline void change(int x,int y){
    if(x>=1&&x<=n&&y>=1&&y<=n){
        if(usearr[x][y])usearr[x][y]=false;
        else usearr[x][y]=true;
    }
}
inline void btnpress(int x,int y){
    change(x,y);
    change(x-1,y);
    change(x+1,y);
    change(x,y+1);
    change(x,y-1);
}
void pressline(int x){
    if(x==1){
        for(int i=1;i<=n;i++){
            if(press[1][i])btnpress(1,i);
        }
        return;
    }
    for(int i=1;i<=n;i++){
        if(usearr[x-1][i]==false){
            btnpress(x,i);
            press[x][i]=true;
        }else press[x][i]=false;
    }
}
void evaluate(){
    memcpy(usearr,array,sizeof(array));
    pressline(1);
    for(int i=2;i<=n;i++){
        pressline(i);
    }
    bool flag=true;
    for(int i=1;i<=n;i++){
        if(usearr[n][i]==false){
            flag=false;
            break;
        }
    }
    if(flag){
        int t=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(press[i][j])t++;
            }
        }
        if(t<max_n)max_n=t;
    }
}
void enumerate(int num){
    if(num==n){
        press[1][num]=false;
        evaluate();
        press[1][num]=true;
        evaluate();
    }else{
        press[1][num]=false;
        enumerate(num+1);
        press[1][num]=true;
        enumerate(num+1);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            char c;
            cin>>c;
            array[i][j]=(c=='y'?true:false);
        }
    }
    enumerate(1);
    if(max_n==1e9)cout<<"inf";
    else cout<<max_n;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注