poj 3279(开关问题)(待完成)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 using namespace std;
 5 #define mem(a,b) (memset(a,b,sizeof a))
 6 const int maxn=15+50;
 7 
 8 int m,n;
 9 int tile[maxn][maxn];
10 int f[maxn][maxn];
11 int res[maxn][maxn];
12 int times;
13 bool isWhite(int x,int y)
14 {
15     return (f[x][y]+f[x-1][y]+f[x][y+1]+f[x][y-1]+tile[x][y])%2;
16 }
17 void Solve()
18 {
19     times=-1;
20     mem(res,0);
21     for(int i=0;i < (1<<n);++i)
22     {
23         mem(f,0);
24         int index=n;
25         int num=i;
26         /*
27         for(int j=1;j <= n;++j)
28             f[1][j]= (i>>(j-1)&1);
29         */
30         do
31         {
32             f[1][index--]=num%2;
33             num >>= 1;
34         }while(num != 0 && index > 0);
35         for(int j=2;j <= m;++j)
36             for(int k=1;k <= n;++k)
37                 if(isWhite(j-1,k) != 0)
38                     f[j][k]=1;
39 
40         bool flag=false;
41         for(int k=1;k <= n;++k)
42             if(isWhite(m,k) != 0)
43                 flag=true;
44         if(!flag)
45         {
46             int cnt=0;
47             for(int j=1;j <= m;++j)
48                 for(int k=1;k <= n;++k)
49                     cnt += f[j][k];
50             if(times == -1 || times > cnt)
51             {
52                 times=cnt;
53                 memcpy(res,f,sizeof f);
54             }
55         }
56     }
57     if(times == -1)
58         printf("IMPOSSIBLE
");
59     else
60         for(int i=1;i <= m;++i)
61             for(int j=1;j <= n;++j)
62                 printf("%d%c",res[i][j],j == n ? '
':' ');
63 }
64 int main()
65 {
66     scanf("%d%d",&m,&n);
67     for(int i=1;i <= m;++i)
68         for(int j=1;j <= n;++j)
69             scanf("%d",&tile[i][j]);
70     Solve();
71 }
View Code