POJ 1753 Flip Game【枚举】

时间:2022-11-14 07:40:03

题目链接:

http://poj.org/problem?id=1753

题意:

由白块黑块组成的4*4方格,每次换一个块的颜色,其上下左右的块也会被换成相反的颜色。问最少换多少块,使得最终方格变为全白或者全黑~

分析:

典型的枚举。

这种问题被称为开关问题,关键是要对周围的块翻动对自身的影响进行记录。后一排决定了前一排的最终状态,枚举第一排的情况即可。

代码:

#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 10, INF = 0x3f3f3f3f;
int a[maxn][maxn];
int m[maxn][maxn], s[maxn][maxn];
int dx[4] = {-1, 0, 0, 1};
int dy[4] = {0, 1, -1, 0};
int check(int row, int color)
{
int cnt = 0;
for(int i = 1; i <= 4; i++){
int tmp = (m[row - 1][i] + s[row - 1][i]) % 2 ;
if((a[row - 1][i] != color && tmp == 0)|| (a[row - 1][i] == color && tmp)){
m[row][i] = 1;
cnt++;
for(int j = 0; j < 4; j++){
s[row + dx[j]][i + dy[j]]++;
}
}
}
return cnt;
}
int solve(int color)
{
int res = INF;
for(int i = 0; i < 16; i++){
memset(s, 0, sizeof(s));
memset(m, 0,sizeof(m));
int cnt = 0;
for(int j = 1; j <= 4; j++){
m[1][j] = (i >> (4- j))&1;
if(m[1][j]){
cnt++;
for(int k = 0; k < 4 ; k++)
s[1+dx[k]][j+dy[k]]++;
}
}
for(int i = 2; i <= 4; i++)
cnt += check(i, color);
if(check(5, color)) cnt = INF;
res = min(res, cnt);
}
return res;
}
int main (void)
{
char t;
int cnt = 0;
for(int i = 1; i <= 4; i++){
for(int j = 1; j <= 4; j++){
cin>>t;
if(t == 'b'){
cnt++;
a[i][j] = 0;
}else a[i][j] = 1;
}
}
if(cnt == 16||cnt == 0) return cout<<0<<endl,0;
// cout<<solve(1)<<' '<<solve(0)<<endl;
int res = min(solve(1),solve(0));
if(res == INF) cout<<"Impossible"<<endl;
else cout<<res<<endl; return 0;
}