首页 > 代码库 > POJ 1681 Painter's Problem (高斯消元)

POJ 1681 Painter's Problem (高斯消元)

题目链接

题意:

一个n*n 的木板 ,每个格子 都 可以 染成 白色和黄色,( 一旦我们对也个格子染色 ,他的上下左右 都将改变颜色);

给定一个初始状态 , 求将 所有的 格子 染成黄色 最少需要染几次?  若 不能 染成 输出 inf。

分析:

和1222差不多,唯一的区别是这个题还要求 最短的步数,其实只需要枚举一下最后的x[][]是否为1,即是否需要按下,

由于只有无解或者解唯一,因为按的顺序是没有影响的,所以只要是有解一定唯一,而且最短的情况是每个格子只按一次,

因为按两次以后就变为原来的状态了。

这个AC代码是我按照模板改的:

  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 using namespace std; 10 int equ, var, fn; 11 int a[maxn][maxn], x[maxn]; 12 int gcd(int a, int b) 13 { 14     return b==0?a:gcd(b, a%b); 15 } 16 int lcm(int a, int b) 17 { 18     return a*b/gcd(a, b); 19 } 20 int Gauss() 21 { 22     int x_mo; 23     x_mo = 2; 24     int i, j, k, max_r, col; 25     int ta, tb, LCM, tmp; 26     col = 0; 27  28     for(k = 0; k<equ && col<var; k++, col++) 29     { 30         max_r = k; 31         for(i = k+1; i < equ; i++) 32             if(abs(a[i][col])>abs(a[max_r][col])) 33             max_r = i; 34  35         if(max_r != k) 36             for(j = k; j < var+1; j++) 37             swap(a[k][j], a[max_r][j]); 38  39         if(a[k][col]==0) 40         { 41             k--; 42             continue; 43         } 44         for(i = k+1; i < equ; i++) 45         { 46             if(a[i][col] != 0) 47             { 48                 LCM = lcm(abs(a[i][col]), abs(a[k][col])); 49                 ta = LCM/abs(a[i][col]); 50                 tb= LCM/abs(a[k][col]); 51                 if(a[i][col]*a[k][col] < 0) tb = -tb; 52  53                 for(j = col; j < var+1; j++) 54                 a[i][j] = ((a[i][j]*ta - a[k][j]*tb)%x_mo+x_mo)%x_mo; 55             } 56         } 57     } 58     for(i = k; i < equ; i++) 59     if(a[i][col] != 0) 60     return -1; 61  62     for(i = var-1; i >= 0; i--) 63     { 64         tmp = a[i][var]; 65         for(j = i+1; j < var; j++) 66         if(a[i][j] != 0) 67         tmp = ((tmp-a[i][j]*x[j])%x_mo+x_mo)%x_mo; 68         if(a[i][i]==0)  //注意这a[i][i]可能为0, 我改为这样就对了。 69         x[i] = 0; 70         else 71         { 72             while(tmp%a[i][i]!=0) tmp += x_mo; 73             x[i] = (tmp/a[i][i])%x_mo; 74         } 75     } 76     return 0; 77 } 78  79 int main() 80 { 81     int t, i, j, n, ans, tmp; 82     char s[maxn]; 83     scanf("%d", &t); 84     while(t--) 85     { 86         memset(a, 0, sizeof(a)); 87         memset(x, 0, sizeof(x)); 88         scanf("%d", &n); 89         equ = n*n; 90         var = n*n; 91         for(i = 0; i < n; i++) 92         { 93             getchar(); 94             scanf("%s", s); 95             for(j = 0; j < n; j++) 96             { 97                 if(s[j]==y) a[i*n+j][n*n] = 0; //y时为0 98                 else a[i*n+j][n*n] = 1; 99             }100         }101         for(i = 0; i < n; i++)102         for(j = 0; j < n; j++)103         {104             tmp = i*n+j;105             a[tmp][tmp] = 1;106             if(j<=n-2)107             a[tmp+1][tmp] = 1;108             if(j>=1)109             a[tmp-1][tmp] = 1;110             if(tmp+n<n*n)111             a[tmp+n][tmp] = 1;112             if(tmp-n>=0)113             a[tmp-n][tmp] = 1;114         }115         fn = Gauss();116         if(fn==-1)117         printf("inf\n");118         else119         {120             ans = 0;121             for(i = 0; i < n*n; i++)122             if(x[i]==1)  //枚举解为1,就是需要将原来的翻转的。123             ans ++;124             printf("%d\n", ans);125         }126     }127     return 0;128 }

 

这个AC代码的模板用的是别人的对二取模的模板,用的是 ^异或,不会出现除0的情况。

  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 using namespace std; 10 int equ, var, fn; 11 int a[maxn][maxn], x[maxn]; 12 int gcd(int a, int b) 13 { 14     return b==0?a:gcd(b, a%b); 15 } 16 int lcm(int a, int b) 17 { 18     return a*b/gcd(a, b); 19 } 20 int  Gauss() 21 { 22     int i,j,k; 23     int max_r; 24     int col; 25     int temp; 26  27     int free_x_num; 28     int free_index; 29  30     col=0; 31     for(k=0;k<equ&&col<var;k++,col++) 32     { 33         max_r=k; 34         for(i=k+1;i<equ;i++) 35         { 36             if(abs(a[i][col])>abs(a[max_r][col]))max_r=i; 37         } 38         if(max_r!=k) 39         { 40             for(j=col;j<var+1;j++)swap(a[k][j],a[max_r][j]); 41         } 42         if(a[k][col]==0) 43         { 44             k--; 45             continue; 46         } 47         for(i=k+1;i<equ;i++) 48         { 49             if(a[i][col]!=0) 50             { 51                 for(j=col;j<var+1;j++) 52                   a[i][j]^=a[k][j]; 53             } 54         } 55     } 56     for(i=k;i<equ;i++) 57     { 58         if(a[i][col]!=0)return -1; 59     } 60     for(i=var-1;i>=0;i--) 61     { 62         x[i]=a[i][var]; 63         for(j=i+1;j<var;j++) 64           x[i]^=(a[i][j]&&x[j]); 65     } 66     return 0; 67 } 68  69 int main() 70 { 71     int t, i, j, n, ans, tmp; 72     char s[maxn]; 73     scanf("%d", &t); 74     while(t--) 75     { 76         memset(a, 0, sizeof(a)); 77         memset(x, 0, sizeof(x)); 78         scanf("%d", &n); 79         equ = n*n; 80         var = n*n; 81         for(i = 0; i < n; i++) 82         { 83             getchar(); 84             scanf("%s", s); 85             for(j = 0; j < n; j++) 86             { 87                 if(s[j]==y) a[i*n+j][n*n] = 0; 88                 else a[i*n+j][n*n] = 1; 89             } 90         } 91         for(i = 0; i < n; i++) 92         for(j = 0; j < n; j++) 93         { 94             tmp = i*n+j; 95             a[tmp][tmp] = 1; 96             if(j<=n-2) 97             a[tmp+1][tmp] = 1; 98             if(j>=1) 99             a[tmp-1][tmp] = 1;100             if(tmp+n<n*n)101             a[tmp+n][tmp] = 1;102             if(tmp-n>=0)103             a[tmp-n][tmp] = 1;104         }105         fn = Gauss();106         if(fn==-1)107         printf("inf\n");108         else109         {110             ans = 0;111             for(i = 0; i < n*n; i++)112             if(x[i]==1)113             ans ++;114             printf("%d\n", ans);115         }116     }117     return 0;118 }