POJ 1681 Painter's Problem （高斯消元枚举自由变元求最小的步数）

题目链接

题意：

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

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

分析：

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

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

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

这个是最严谨的这个题的AC代码，因为我做1753的时候用原来的方法错了，看了Kuangbin的博客，知道原来的方法不对，貌似只有一个解和无解的时候才会对。

但是这个是对的：

  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 -1;
 64     
 65     //以下为模2情况下的，枚举变元的方法。
 66     int stat=1<<(var-k);//自由变元有 var-k 个
 67     int res=INF;
 68     for(i=0;i<stat;i++)//枚举所有变元
 69     {
 70         int cnt=0;
 71         int index=i;
 72         for(j=0;j<var-k;j++)
 73         {
 74             x[free_x[j]]=(index&1);
 75             if(x[free_x[j]]) cnt++;
 76             index>>=1;
 77         }
 78         for(j=k-1;j>=0;j--)
 79         {
 80             int tmp=a[j][var];
 81             for(int l=j+1;l<var;l++)
 82               if(a[j][l]) tmp^=x[l];
 83             x[j]=tmp;
 84             if(x[j])cnt++;
 85         }
 86         if(cnt<res)res=cnt;
 87     }
 88     return res;
 89 }
 90 
 91 int main()
 92 {
 93     int t, i, j, n, tmp;
 94     char s[maxn];
 95     scanf("%d", &t);
 96     while(t--)
 97     {
 98         memset(a, 0, sizeof(a));
 99         memset(x, 0, sizeof(x));
100         scanf("%d", &n);
101         equ = n*n;
102         var = n*n;
103         for(i = 0; i < n; i++)
104         {
105             getchar();
106             scanf("%s", s);
107             for(j = 0; j < n; j++)
108             {
109                 if(s[j]=='y') a[i*n+j][n*n] = 0; //y时为0
110                 else a[i*n+j][n*n] = 1;
111             }
112         }
113         for(i = 0; i < n; i++)
114         for(j = 0; j < n; j++)
115         {
116             tmp = i*n+j;
117             a[tmp][tmp] = 1;
118             if(j<=n-2)
119             a[tmp+1][tmp] = 1;
120             if(j>=1)
121             a[tmp-1][tmp] = 1;
122             if(tmp+n<n*n)
123             a[tmp+n][tmp] = 1;
124             if(tmp-n>=0)
125             a[tmp-n][tmp] = 1;
126         }
127         fn = Gauss();
128         if(fn==-1)
129         printf("inf
");
130         else
131         printf("%d
", fn);
132     }
133     return 0;
134 }

这个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
");
118         else
119         {
120             ans = 0;
121             for(i = 0; i < n*n; i++)
122             if(x[i]==1)  //枚举解为1，就是需要将原来的翻转的。
123             ans ++;
124             printf("%d
", 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
");
108         else
109         {
110             ans = 0;
111             for(i = 0; i < n*n; i++)
112             if(x[i]==1)
113             ans ++;
114             printf("%d
", ans);
115         }
116     }
117     return 0;
118 }

POJ 1681 Painter's Problem （高斯消元 枚举自由变元求最小的步数）

POJ 1681 Painter's Problem （高斯消元枚举自由变元求最小的步数）