首页 > 代码库 > POJ 1753 Flip Game （高斯消元 枚举自由变元求最小步数）

POJ 1753 Flip Game （高斯消元 枚举自由变元求最小步数）

2024-07-18 07:57:15   229人阅读

题目链接

题意：4*4的黑白棋，求把棋全变白或者全变黑的最小步数。

分析：以前用状态压缩做过。 和上题差不多，唯一的不同是这个终态是黑棋或者白棋，

但是只需要把给的初态做不同的两次处理就行了。

感觉现在还只是会套模板，不能独立的思考，好伤心。。。。

  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <cstdlib>  5 #include <cmath>  6 #include <algorithm>  7 #define LL __int64  8 const int maxn = 300+10;  9 const int INF = 1<<28; 10 using namespace std; 11 int equ, var, fn; 12 int a[maxn][maxn], x[maxn]; 13 int free_x[maxn]; 14 int gcd(int a, int b) 15 { 16     return b==0?a:gcd(b, a%b); 17 } 18 int lcm(int a, int b) 19 { 20     return a*b/gcd(a, b); 21 } 22 int Gauss() 23 { 24     int x_mo; 25     x_mo = 2; 26     int i, j, k, max_r, col; 27     int ta, tb, LCM, fx_num = 0; 28     col = 0; 29  30     for(k = 0; k<equ && col<var; k++, col++) 31     { 32         max_r = k; 33         for(i = k+1; i < equ; i++) 34             if(abs(a[i][col])>abs(a[max_r][col])) 35                 max_r = i; 36  37         if(max_r != k) 38             for(j = k; j < var+1; j++) 39                 swap(a[k][j], a[max_r][j]); 40  41         if(a[k][col]==0) 42         { 43             free_x[fx_num++] = col; //求自由变元所在的列 44             k--; 45             continue; 46         } 47         for(i = k+1; i < equ; i++) 48         { 49             if(a[i][col] != 0) 50             { 51                 LCM = lcm(abs(a[i][col]), abs(a[k][col])); 52                 ta = LCM/abs(a[i][col]); 53                 tb= LCM/abs(a[k][col]); 54                 if(a[i][col]*a[k][col] < 0) tb = -tb; 55  56                 for(j = col; j < var+1; j++) 57                     a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%x_mo+x_mo)%x_mo; 58             } 59         } 60     } 61     for(i = k; i < equ; i++) 62         if(a[i][col] != 0) 63             return INF; 64  65     int stat=1<<(var-k); 66     int res=INF; 67     for(i=0; i<stat; i++) 68     { 69         int cnt=0; 70         int index=i; 71         for(j=0; j<var-k; j++) 72         { 73             x[free_x[j]]=(index&1); 74             if(x[free_x[j]]) cnt++; 75             index>>=1; 76         } 77         for(j=k-1; j>=0; j--) 78         { 79             int tmp=a[j][var]; 80             for(int l=j+1; l<var; l++) 81                 if(a[j][l]) tmp^=x[l]; 82             x[j]=tmp; 83             if(x[j])cnt++; 84         } 85         if(cnt<res)res=cnt; 86     } 87     return res; 88 } 89  90 void init() 91 { 92     int i, j, tmp; 93     memset(a, 0, sizeof(a)); 94     memset(x, 0, sizeof(x)); 95     for(i = 0; i < 4; i++) 96         for(j = 0; j < 4; j++) 97         { 98             tmp = i*4+j; 99             a[tmp][tmp] = 1;100             if(j<=4-2)101                 a[tmp+1][tmp] = 1;102             if(j>=1)103                 a[tmp-1][tmp] = 1;104             if(tmp+4<4*4)105                 a[tmp+4][tmp] = 1;106             if(tmp-4>=0)107                 a[tmp-4][tmp] = 1;108         }109 }110 int main()111 {112     int i, j, ans;113     char s[maxn][maxn];114     while(~scanf("%s", s[0]))115     {116         equ = 16;117         var = 16;118         for(i = 1; i < 4; i++)119         {120             getchar();121             scanf("%s", s[i]);122         }123         init();124         for(i = 0; i < 4; i++)125             for(j = 0; j < 4; j++)126             {127                 if(s[i][j]==‘b‘) a[i*4+j][16] = 0;128                 else a[i*4+j][16] = 1;129             }130         fn = Gauss();131 132         init();133         for(i = 0; i < 4; i++)134             for(j = 0; j < 4; j++)135             {136                 if(s[i][j]==‘w‘) a[i*4+j][16] = 0;137                 else a[i*4+j][16] = 1;138             }139         int fn2 = Gauss();140         if(fn==INF&&fn2==INF)141             printf("Impossible\n");142 143         else144         {145             ans = min(fn, fn2);146             printf("%d\n", ans);147         }148     }149     return 0;150 }

 


联系
我们