poj 1753 Flip Game 高斯消元

题目链接

4*4的格子, 初始为0或1, 每次翻转一个会使它四周的也翻转, 求翻转成全0或全1最少的步数。

#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
int a[][], ans[], x[];
int n, l[], free_x[];
int gauss(int equ,int var)
{
int i,j,k, max_r, col = , temp, free_index, num = ;
for(int i=;i<=var;i++)
{
x[i]=;
free_x[i]=;
}
for(k = ;k < equ && col < var;k++,col++)
{
max_r=k;
for(i=k+;i<equ;i++)
{
if(abs(a[i][col])>abs(a[max_r][col])) max_r=i;
}
if(max_r!=k)
{
for(j=k;j<var+;j++) swap(a[k][j],a[max_r][j]);
}
if(a[k][col]==)
{
k--;
free_x[num++]=col;
continue;
}
for(i=k+;i<equ;i++)
{
if(a[i][col]!=)
{
for(j=col;j<var+;j++)
{
a[i][j] ^= a[k][j];
}
}
}
}
for (i = k; i < equ; i++)
{
if (a[i][col] != ) return inf;
}
int stat = <<(var-k);
int res = inf;
for(i=;i<stat;i++)
{
int cnt=;
int index=i;
for(j=;j<var-k;j++)
{
x[free_x[j]]=(index&);
if(x[free_x[j]]) cnt++;
index>>=;
}
for(j=k-;j>=;j--)
{
int tmp=a[j][var];
int t=;
while(a[j][t]==)t++;
for(int l=t+;l<var;l++)
if(a[j][l]) tmp^=x[l];
x[t]=tmp;
if(x[t])cnt++;
}
if(cnt<res)res=cnt;
}
return res;
}
void init() {
mem(a);
for(int i = ; i<; i++) {
for(int j = ; j<; j++) {
a[i*+j][i*+j] = ;
for(int k = ; k<; k++) {
int x = dir[k][]+i;
int y = dir[k][]+j;
if(x>=&&x<&&y>=&&y<) {
a[i*+j][x*+y] = ;
}
}
}
}
}
int main()
{
char c[][];
for(int i = ; i<; i++) {
cin>>c[i];
}
init();
for(int i = ; i<; i++) {
for(int j = ; j<; j++) {
if(c[i][j] == 'b')
a[i*+j][] = ;
else
a[i*+j][] = ;
}
}
int ans = gauss(, );
init();
for(int i = ; i<; i++) {
for(int j = ; j<; j++) {
if(c[i][j] == 'w')
a[i*+j][] = ;
else
a[i*+j][] = ;
}
}
ans = min(ans, gauss(, ));
if(ans == inf) {
cout<<"Impossible"<<endl;
} else {
cout<<ans<<endl;
}
return ;
}
上一篇:POJ 1753 Flip game ( 高斯消元枚举*变量)


下一篇:ASP实现https和http之间转化