poj 3279 Fliptile (搜索..暴力？)
http://poj.org/problem?id=3279
反转类问题.
有N*M个方格,每个上面有数字0或者1
操作一个方格,这个方格即其相邻的四个方格(有公共边)会改变状态(由0变1或者由1变0)
问至少需要多少次操作,所有的状态都为0
如果有多组,输出字典序小的那一组.
跟开关灯的那题相似.
因为每个开关灯的动作还影响其他相邻灯的状态.所以对于这种题,一般思路是,先定住一部分,再由已知定住的这部分去确定其他部分.
对于这道题而言
首先我们可以很容易发现,操作数为偶数和为0是等价的.
操作数为1和为奇数是等价的.
对于这道题而言,我们可以首先枚举第一行的状态,一共有 2<
然后如果 a[i-1][j]为1,因为i-1行的状态已经确定,无法改变,所以能影响到a[i-1][j]的只有a[i][j]
那么a[i][j]一定要操作一次
最后判断最后一行是否都为0,如果为0,表示这种情况是合法的
然后找到操作数最小的一组.
字典序的话,只要是枚举的时候按照数的大小顺序就可以保证.
学会了用memcpy函数.
1
2 #include<iostream>
3 #include<iomanip>
4 #include<cstdio>
5 #include<algorithm>
6 #include<cmath>
7 #include<cstring>
8 #include<string>
9 #include<map>
10 #include<set>
11 #include<queue>
12 #include<vector>
13 #include<stack>
14 #define y0 abc111qqz
15 #define y1 hust111qqz
16 #define yn hez111qqz
17 #define j1 cute111qqz
18 #define tm crazy111qqz
19 #define lr dying111qqz
20 using namespace std;
21 #define REP(i, n) for (int i=0;i<int(n);++i)
22 typedef long long LL;
23 typedef unsigned long long ULL;
24 const int N=20;
25 int a[N][N],ans[N][N],op[N][N];
26 int m,n;
27 int dirx[10]={0,0,0,-1,1};
28 int diry[10]={0,1,-1,0,0};
29 int rec[N][N];
30 void solve(int x,int y)
31 {
32 for ( int i = 0 ; i < 5 ; i++ )
33 {
34 int newx = x + dirx[i];
35 int newy = y + diry[i];
36 if (newx>=1&&newx<=m&&newy>=1&&newy<=n)
37 {
38 a[newx][newy]=a[newx][newy]^1;
39 }
40 }
41 }
42 bool on (int x,int y)
43 {
44 int res = a[x][y];
45 for ( int i = 0 ; i < 5 ; i++ )
46 {
47 int newx = x + dirx[i];
48 int newy = y + diry[i];
49 if (newx>=1&&newx<=m&&newy>=1&&newy<=n)
50 {
51 res = res+op[newx][newy];
52 }
53
54 }
55 return res&1;
56 }
57 int main()
58 {
59 cin>>m>>n;
60 int mi = 9999999;
61 memset(rec,0,sizeof(rec));
62 for ( int i = 1 ; i <= m ; i++ )
63 {
64 for (int j = 1 ; j <= n ; j++)
65 {
66 cin>>a[i][j];
67 }
68 }
69 bool flag = false;
70 for ( int i = 0 ; i < (1<<n); i++ ) //枚举第一行的好改变情况
71 {
72 int tmp=i;
73 int num=0;
74 memset(op,0,sizeof(op));
75 memset(ans,0,sizeof(ans));
76 int k = n;
77 while (tmp)
78 {
79 op[1][k]=tmp%2;
80 if (op[1][k]==1) num++;
81 tmp = tmp / 2;
82 k--;
83 }
84 // cout<<"********************"<<endl;
85 // for ( int i = 1 ; i <= n ; i++)
86 // {
87 // cout<<op[1][i]<<" ";
88 // }
89 // cout<<endl;
90 // cout<<"*************************"<<endl;
91
92
93 for ( int j = 2 ; j <= m ; j++ )
94 {
95 for ( int k = 1 ; k <= n ; k++ )
96 {
97 if (on(j-1,k))
98 {
99 op[j][k]=1;
100 num++;
101 }
102 }
103 }
104 bool ok = true;
105 for ( int j = 1 ; j <= n ; j++ )
106 {
107 if (on(m,j))
108 {
109 ok=false;
110 break;
111 }
112 }
113 if (ok)
114 {
115 flag = true;
116 if (num<mi)
117 {
118 mi = num;
119 memcpy(rec,op,sizeof(op));
120 // for ( int j = 1 ; j <= m ; j ++ )
121 // {
122 // for ( int k = 1 ; k <= n ; k++ )
123 // {
124 // rec[j][k]=ans[j][k];
125 // }
126 // }
127 }
128 }
129 }
130 if (flag)
131 {
132 for ( int i = 1 ; i <= m ; i++ )
133 {
134 cout<<rec[i][1];
135 for ( int j = 2 ; j <= n ; j++ )
136 {
137 cout<<" "<<rec[i][j];
138 }
139 cout<<endl;
140 }
141 }
142 else
143 {
144 printf("IMPOSSIBLE\n");
145 }
146
147 return 0;
148 }
149