Painter's Problem

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #include<queue>
 8 #include<vector>
 9 using namespace std;
10 int T,N,ANS;
11 int a[300][300];
12 bool gauss(){
13     int now=1;
14     for(int i=1;i<=N*N;i++){
15         int to=now;
16         while(to<=N*N&&a[to][i]==0) to++;
17         if(to>N*N) continue;
18         if(to!=now){
19             for(int j=1;j<=N*N+1;j++) swap(a[to][j],a[now][j]);
20         }
21         for(int j=1;j<=N*N;j++){
22             if(j!=now&&a[j][i]){
23                 for(int k=1;k<=N*N+1;k++){
24                     a[j][k]^=a[i][k];
25                 }
26             }
27         }
28         now++;
29     }
30     for(int i=now;i<=N*N;i++)
31         if(a[i][N*N+1]!=0) return false;
32     return true;
33 }
34 
35 int v[300],cnt;
36 void dfs(int x){
37     if(cnt>=ANS) return ;//已经比目前的答案大了，没有必要再搜 
38     if(x==0){
39         ANS=min(cnt,ANS);
40         return ;
41     }
42     if(a[x][x]!=0){
43         int num=a[x][N*N+1];//num表示第x块砖染色不染色 
44         for(int i=x+1;i<=N*N;i++){
45             if(a[x][i]!=0) num=num^v[i];//已经枚举过的x+1~N*N中某块砖如果可以对x产生影响且已染色，就让num改变一次 
46         }
47         v[x]=num;
48         if(num==1) cnt++;
49         dfs(x-1);
50         if(num==1) cnt--;
51     }
52     else{//枚举按或不按两种情况 
53         v[x]=0; dfs(x-1);
54         v[x]=1; cnt++; dfs(x-1); cnt--;
55     }
56 }
57 
58 int main(){
59     scanf("%d",&T);
60     while(T--){
61         memset(a,0,sizeof(a));
62         scanf("%d",&N);
63         for(int i=1;i<=N*N;i++){
64             a[i][i]=1;
65             if(i%N!=1) a[i][i-1]=1;
66             if(i%N!=0) a[i][i+1]=1;
67             if(i>=N+1) a[i][i-N]=1;
68             if(i<=N*(N-1)) a[i][i+N]=1;    
69         }
70         for(int i=1;i<=N;i++){
71             char s[300];
72             scanf("%s",s+1);
73             for(int j=1;j<=N;j++){
74                 if(s[j]==‘w‘) a[(i-1)*N+j][N*N+1]=1; 
75             }
76         }
77         if(gauss()==false){
78             puts("inf");
79             continue;
80         }
81         ANS=1<<28;
82         dfs(N*N);
83         printf("%d\n",ANS);
84     }
85     return 0;
86 }