首页 > 代码库 > poj 1753 Flip Game(高斯消元)
poj 1753 Flip Game(高斯消元)
http://poj.org/problem?id=1753
因为目标状态是全白或全黑,所以进行两次高斯消元,每次若有自由变元的话要枚举自由变元求得最优解。
哇哦,怎么就写了200+行。
#include <stdio.h> #include <iostream> #include <map> #include <set> #include <stack> #include <vector> #include <math.h> #include <string.h> #include <queue> #include <string> #include <stdlib.h> #include <algorithm> #define LL long long #define _LL __int64 #define eps 1e-12 #define PI acos(-1.0) #define C 240 #define S 20 using namespace std; const int INF = 0x3f3f3f3f; int equ = 16; int var = 16; int x[20]; int a[20][20]; char s[5][5]; int x_free[20]; int free_num; int Gauss() { int row,col,max_r,i,j; row = col = 0; free_num = 0; while(row < equ && col < var) { max_r = row; for(i = row+1; i < equ; i++) { if(abs(a[i][col]) > abs(a[max_r][col])) max_r = i; } if(max_r != row) { for(j = col; j <= var; j++) swap(a[max_r][j],a[row][j]); } if(a[row][col] == 0) { x_free[free_num++] = col; col++; continue; } for(i = row+1; i < equ; i++) { if(a[i][col] == 0) continue; for(j = col; j <= var; j++) a[i][j] ^= a[row][j]; } row++; col++; } for(i = row; i < equ; i++) if(a[i][var] != 0) return -1; if(row < var) return var - row; for(i = var-1; i >= 0; i--) { x[i] = a[i][var]; for(j = i+1; j < var; j++) x[i] ^= (a[i][j] && x[j]); } return 0; } int solve() { int t = Gauss(); int res; if(t == -1) return -1; else if(t == 0) { res = 0; for(int i = 0; i < 16; i++) res += x[i]; return res; } else if(t > 0) { int ans = INF; for(int i = 0; i < (1<<t); i++) { res = 0; for(int j = 0; j < t; j++) { if(i&(1<<j)) { x[x_free[j]] = 1; res++; } else x[x_free[j]] = 0; } int k; for(int j = var-t-1; j >= 0; j--) { for(k = j; k < var; k++) if(a[j][k]) break; x[k] = a[j][var]; for(int l = k+1; l < var; l++) if(a[j][l]) x[k] ^= x[l]; res += x[k]; } ans = min(ans,res); } return ans; } } void init() { memset(a,0,sizeof(a)); memset(x,0,sizeof(x)); for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { int num = i*4+j; a[num][num] = 1; if((i-1) >= 0) a[(i-1)*4+j][num] = 1; if((i+1) <= 3) a[(i+1)*4+j][num] = 1; if((j-1) >= 0) a[i*4+j-1][num] = 1; if((j+1) <= 3) a[i*4+j+1][num] = 1; } } } int main() { int s1,s2; for(int i = 0; i < 4; i++) { scanf("%s",s[i]); } init(); for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { if(s[i][j] == 'b') a[i*4+j][16] = 0; else if(s[i][j] == 'w') a[i*4+j][16] = 1; } } int sum = 0; for(int i = 0; i < 16; i++) { if(a[i][16] == 1) sum += (1 << i); } if(sum == 0 || sum == 65535) { printf("0\n"); return 0; } s1 = solve(); init(); for(int i = 0; i < 4; i++) { for(int j = 0; j < 4; j++) { if(s[i][j] == 'b') a[i*4+j][16] = 1; else if(s[i][j] == 'w') a[i*4+j][16] = 0; } } s2 = solve(); if(s1 == -1 && s2 == -1) printf("Impossible\n"); else if(s1 == -1 && s2 != -1) printf("%d\n",s2); else if(s1 != -1 && s2 == -1) printf("%d\n",s1); else printf("%d\n",min(s1,s2)); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。