POJ 1753 Flip Game（高斯消元入门超详细题解）——Northeastern Europe 2000
2016-09-06 09:26:10         来源：ITAK

Flip Game

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Flip game is played on a rectangular4×44×4field with two-sided pieces placed on each of its1616squares. 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 flip33to55pieces, 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:

Choose any one of the1616pieces. 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`bdenotes pieces lying their black side up andwdenotes pieces lying their white side up. If we choose to flip the1st1stpiece from the3rd3rdrow (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`

`There are only one test case in the input file.`

`The input consists of44lines with44charactersworbeach 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 wordImpossible(without quotes).`

`Sample input and output`

`Sample Input` `Sample Output`
``````bwwb
bbwb
bwwb
bwww``````
``4``

`Source`

```Northeastern Europe 2000 题目大意： 有一个 4*4 的矩阵，然后现在每个格子有两个颜色，要么是黑色，要么是白色，当你的手按动一个格子的时候，这个格子的上、下、左、右都会 改变原来的颜色，即由黑变白，由白变黑，现在问你的是，经过最少几次翻转之后可以使得这个 4*4 的矩阵变为全是白色的或者是全是黑色的。 解题思路： 因为我们学过高斯消元，这也是一道高斯消元的入门题目，首先考虑有 4*4 个格子，然后根据每一个格子列出一个方程，也就是有 16 个方程， 16 个未知数，其实高斯消元，怎么消呢，首先我们得有几个方程，如果我们连方程都列不出来就不用解了，那么我们现在就来列方程： ```
 `按第1个格` `按第2个格` `按第3个格` `按第4个格` `第1个格` `1` `1` `0` `0` `第2个格` `1` `1` `1` `0` `第3个格` `0` `1` `1` `1` `第4个格` `0` `0` `1` `1` `第5个格` `1` `0` `0` `0` `第6个格` `0` `1` `0` `0` `第7个格` `0` `0` `1` `0` `第8个格` `0` `0` `0` `1`

```现在我来说一下上述表格的一次：纵的表示的是按动第几个格子；横的表示的是按动第 j 个格子的时候，跟着 j 这个格子变化的是第几个格子， 如果变化就设为 1 ，否则设为 0。根据上述一样的这个表格我们就可以列出方程啦。因为解方程解得是 AX = B 现在A 我们已经知道了，那个 B 就是 给定的初始状态，也就是增广矩阵中的最后一列，最后我们消元后发现：有 4 个自由变元，又因为 每个自由变元有 两种变化，所以一共有 2^4 = 16 种状态， 然后我们利用二进制枚举（容斥中经常用），挨个枚举状态，从 0000 一直到 1111，然后每次枚举的时候然后回代原先的方程中，得到解 集，然后再解集中找最小值，也就是找 x[i] = 1 的个数，对于这个题来说，先进行求全白的得到一个最小值，然后再将那个 B（增广矩阵中的最后一列） 取反，又得到一个最小值，两个取最小值就行了。当然这个题目也可以不用高斯消元做，毕竟就 4*4 的矩阵。 My Code： ```
``````/**
2016 - 09 - 05 下午
Author: ITAK

Motto:

**/

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 1e9+5;
const int MAXN = 20;
const int MOD = 1e9+7;
const double eps = 1e-7;
const double PI = acos(-1);
using namespace std;
LL Scan_LL()///输入外挂
{
LL res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}
int Scan_Int()///输入外挂
{
int res=0,ch,flag=0;
if((ch=getchar())=='-')
flag=1;
else if(ch>='0'&&ch<='9')
res=ch-'0';
while((ch=getchar())>='0'&&ch<='9')
res=res*10+ch-'0';
return flag?-res:res;
}
void Out(LL a)///输出外挂
{
if(a>9)
Out(a/10);
putchar(a%10+'0');
}
int equ, var;///equ个方程 var个变量
int a[MAXN][MAXN];///增广矩阵
int x[MAXN];///解集
int x_i[MAXN];
bool free_x[MAXN];///判断是不是自由变元
int free_num;///自由变元的个数
inline int GCD(int m, int n)
{
if(n == 0)
return m;
return GCD(n, m%n);
}
inline int LCM(int a, int b)
{
return a/GCD(a,b)*b;
}

int Gauss()
{
int Max_r;///当前列绝对值最大的存在的行
///col：处理当前的列
int row,col = 0;
int free_x_num;
int free_index;
free_num = 0;
for(int i=0; i<=var; i++)
{
x[i] = 0;
free_x[i] = 1;
}
for(row=0; row abs(a[Max_r][col]))
Max_r = i;
if(a[Max_r][col] == 0)
{
free_x[col] = 1;
x_i[free_num++] = col;
}
if(Max_r != row)
for(int i=0; i=0; i--)
{
free_x_num = 0;
for(int j=0; j 1)
continue;
int tmp = a[i][var];
for(int j=0; j=0; i--)
{
int tmp = a[i][var] % 2;
for(int j=i+1; j 0)
a[i-1][i] = 1;
if(tb > 0)
a[i][i-4] = 1;
if(ta < 3)
a[i+1][i] = 1;
if(tb < 3)
a[i][i+4] = 1;
}
}
void Debug()
{
puts("");
cout<<"+++++++++++++++++++++++++++分界线++++++++++++++++++++++++++++++"<=0; ii--)
{
int tmp = a[ii][var] % 2;
for(int j=ii+1; j=0; ii--)
{
int tmp = a[ii][var] % 2;
for(int j=ii+1; j

``````