Flip Game
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 20337 | Accepted: 8821 |
Description
Flip game is played on a rectangular 4x4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules:
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
- Choose any one of the 16 pieces.
- Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any).
Consider the following position as an example:
bwbw
wwww
bbwb
bwwb
Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:
bwbw
bwww
wwwb
wwwb
The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.
Input
The input consists of 4 lines with 4 characters "w" or "b" each that denote game field position.
Output
Write to the output file a single integer number - the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it's impossible to achieve the goal, then write the word "Impossible" (without quotes).
Sample Input
bwwb bbwb bwwb bwww
Sample Output
4
Source
解题：
基本和POJ1222差不多(参见博客POJ1222中内容)
点击打开链接
但是出现行变换后最后四行值均为0 即方程组有无穷解状态 通过最后一行回带一个未知数x (0或1)
那么通过枚举或者搜索找出最小的变换
#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
const int maxn=16;
int a[maxn][maxn+1],x[maxn],b[maxn][maxn+1];
int equ,var;
bool free_x[maxn+1]; // 判断是否是不确定的变元.
int free_num,ans=100000000;
int abs1(int num)
{
if (num>=0) return num;
else
return -1*num;
}
void Debug(void)
{
int i, j;
for (i = 0; i < equ; i++)
{
for (j = 0; j < var + 1; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
}
inline int gcd(int a, int b)
{
int t;
while (b != 0)
{
t = b;
b = a % b;
a = t;
}
return a;
}
inline int lcm(int a, int b)
{
return a * b / gcd(a, b);
}
int dfs(int p) //枚举自由解，只能取0-1，枚举完就回带，找到最小的
{
if (p<=free_num-1) //深入到了主对角线元素非0 的行了
{
//下面就是回带的代码啊
for(int i = free_num-1; i >= 0; --i)
{
int tmp = a[i][var] % 2;
for(int j = i+1; j < var; ++j) //x[i]取决于x[i+1]--x[var]啊，所以后面的解对前面的解有影
//响。
if(a[i][j] != 0)
tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
x[i] = (tmp/a[i][i]) % 2; //上面的正常解
} //回带完成了
//计算解元素为1 的个数；
int sum=0;
for(int i=0; i<var; i++) sum+=x[i];
if (ans>sum) ans=sum;
return 0;
}
x[p]=0;
dfs(p-1);
x[p]=1;
dfs(p-1);
}
void swap(int &a,int &b)
{
int temp=a;
a=b;
b=temp;
}
int Gauss_1()
{
int k,col = 0; //当前处理的列
for(k = 0; k < equ && col < var; ++k,++col)
{
int max_r = k;
for(int i = k+1; i < equ; ++i)
if(a[i][col] > a[max_r][col])
max_r = i;
if(max_r != k)
{
for(int i = k; i < var + 1; ++i)
swap(a[k][i],a[max_r][i]);
}
if(a[k][col] == 0)
{
k--;
continue;
}
for(int i = k+1; i < equ; ++i)
{
if(a[i][col] != 0)
{
int LCM = lcm(a[i][col],a[k][col]);
int ta = LCM/a[i][col], tb = LCM/a[k][col];
if(a[i][col]*a[k][col] < 0)
tb = -tb;
for(int j = col; j < var + 1; ++j)
a[i][j] = ( (a[i][j]*ta)%2 - (a[k][j]*tb)%2 + 2 ) % 2; //a[i][j]只有0 和
//1 两种状态
}
}
}
for(int i = k; i < equ; ++i)
if(a[i][col] != 0) return -1; // 无解返回 -1
//上述代码是消元的过程，消元完成
//Debug();
//唯一解或者无穷解,k<=var
//var-k==0 唯一解；var-k>0 无穷多解，自由解的个数=var-k
//下面这几行很重要，保证秩内每行主元非0，且按对角线顺序排列
for(int i = 0; i <equ; ++i)//每一行主元素化为非零
if(!a[i][i])
{
int j;
for(j = i+1; j<var; ++j)
if(a[i][j])
break;
if(j == var)
break;
for(int k = 0; k < equ; ++k)
swap(a[k][i],a[k][j]);
}
// ----处理保证对角线主元非0 且顺序，完成
free_num=k;
if (var-k>0)
{
dfs(var-1);
return ans;
}
if (var-k==0)//唯一解时，poj1753 本题没唯一解，当题目具体操作给出后，系数矩阵已
//经固定了！
{
//下面是回带求解，当无穷多解时，最后几行为0
for(int i = k-1; i >= 0; --i)
{
int tmp = a[i][var] % 2;
for(int j = i+1; j < var; ++j) //x[i]取决于x[i+1]--x[var]啊，所以后面的解对前面的解有影
//响。
if(a[i][j] != 0)
tmp = ( tmp - (a[i][j]*x[j])%2 + 2 ) % 2;
//if (a[i][i]==0) x[i]=tmp; //最后的空行时，即无穷解得
//else
x[i] = (tmp/a[i][i]) % 2; //上面的正常解
}
int sum=0;
for(int i=0; i<var; i++) sum+=x[i];
return sum;
}
}
int main()
{
int k,free_num;
char c1[20];
memset(a,0,sizeof(a));
memset(x,0,sizeof(x));
ans=1000000000;
for (int i=0; i<4; i++)
{
cin>>c1;
//构造系数矩阵A
for (int j=0; j<4; j++)
{
k = 4*i+j;
a[k][k]=1;
if (i>0) a[k][k-4]=1; //上
if (i<3) a[k][k+4]=1; //下
if (j>0) a[k][k-1]=1; //左
if (j<3) a[k][k+1]=1; //右
if (c1[j]=='b')
a[k][maxn] = 1;
}
}
for(int i=0; i<16; i++)
for(int j=0; j<=16; j++)
b[i][j]=a[i][j];
for(int k=0; k<16; k++)
b[k][16]^=1;
equ=var=16;
int j1=Gauss_1();
int min1=ans;
for(int i=0; i<16; i++)
for(int j=0; j<=16; j++)
a[i][j]=b[i][j];
ans=100000000;
int j2=Gauss_1();
int min2=ans;
if (j1==-1&&j2==-1) cout<<"Impossible"<<endl;
else
cout<<min(ans,min1)<<endl;
// cout << "Hello world!" << endl;
return 0;
}
