状态压缩+枚举 POJ 3279 Fliptile

题目传送门

 /*
题意:问最少翻转几次使得棋子都变白,输出翻转的位置
状态压缩+枚举:和之前UVA_11464差不多,枚举第一行,可以从上一行的状态知道当前是否必须翻转
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; const int MAXN = ;
const int INF = 0x3f3f3f3f;
int a[MAXN][MAXN];
int b[MAXN][MAXN];
int ans[MAXN][MAXN];
int dx[] = {-, , , , };
int dy[] = {, , , -, };
int n, m; int get_col(int x, int y) {
int ret = a[x][y];
for (int i=; i<; ++i) {
int tx = x + dx[i], ty = y + dy[i];
if (tx < || tx >= n || ty < || ty >= m) continue;
ret += b[tx][ty];
}
return ret & ;
} int check(int s) {
memset (b, , sizeof (b));
for (int i=; i<m; ++i) {
if (s & ( << i)) b[][i] = ;
}
for (int i=; i<n; ++i) {
for (int j=; j<m; ++j) {
if (get_col (i-, j)) b[i][j] = ;
}
}
for (int i=; i<m; ++i) if (get_col (n-, i)) return INF;
int ret = ;
for (int i=; i<n; ++i) {
for (int j=; j<m; ++j) ret += b[i][j];
}
return ret;
} int main(void) { //POJ 3279 Fliptile
while (scanf ("%d%d", &n, &m) == ) {
for (int i=; i<n; ++i) {
for (int j=; j<m; ++j) {
scanf ("%d", &a[i][j]);
}
}
int mn = INF;
memset (ans, , sizeof (ans));
for (int i=; i<(<<m); ++i) {
int res = check (i);
if (res < mn) {
mn = res;
for (int i=; i<n; ++i) {
for (int j=; j<m; ++j) {
if (b[i][j]) ans[i][j] = ;
else ans[i][j] = ;
}
}
}
}
if (mn < INF) {
for (int i=; i<n; ++i) {
for (int j=; j<m; ++j) printf ("%d%c", ans[i][j], (j == m-) ? '\n' : ' ');
}
}
else puts ("IMPOSSIBLE");
} return ;
}
上一篇:POJ.3279 Fliptile (搜索+二进制枚举+开关问题)


下一篇:POJ 3279 Fliptile (二进制+搜索)