[Gauss]POJ1681 Painter's Problem

和POJ1222（分析）完全相同
题意也类似，可以涂自己以及上下左右五个位置的颜色
问几次能全部涂色不能输出inf
01方程组用异或来求解就好了
  1 int a[300][300];  // 增广矩阵
  2 int x[300];  // 解
  3 int free_x[300]; // 标记是否为自由未知量
  4 
  5 int n;
  6 void debug()
  7 {
  8     for(int i0=0;i0<n*n;i0++)
  9     {
 10         for(int j0=0;j0<n*n;j0++)
 11             printf("%d ", a[i0][j0]);
 12         printf("
");
 13     }
 14 }
 15 
 16 int Gauss(int n, int m) // n个方程 m个未知数 即 n行m+1列
 17 {
 18     //转换为阶梯形式
 19     int col=0, k, num=0;
 20     for(k=0;k<n && col<m;k++, col++)
 21     {//枚举行
 22         int max_r=k;
 23         for(int i=k+1;i<n;i++)//找到第col列元素绝对值最大的那行与第k行交换
 24             if(abs(a[i][col])>abs(a[max_r][col]))
 25                 max_r=i;
 26         if(max_r!=k)// 与第k行交换
 27             for(int j=col;j<m+1;j++)
 28                 swap(a[k][j], a[max_r][j]);
 29         if(!a[k][col])// 说明该col列第k行以下全是0了
 30         {
 31             k--;
 32             free_x[num++]=col;
 33             continue;
 34         }
 35         for(int i=k+1;i<n;i++)// 枚举要删除的行
 36             if(a[i][col])
 37                 for(int j=col;j<m+1;j++)
 38                     a[i][j]^=a[k][j];
 39     }
 40 
 41 //    debug();
 42 //    printf("%d %d
", col, k);
 43 
 44     for(int i=k;i<n;i++)
 45         if(a[i][col])
 46             return -1; // 无解
 47 
 48 //    if(k<m)   //m-k为自由未知量个数
 49 //    {
 50         int stat=1<<(m-k);
 51         int ans=INT_MAX;
 52         for(int i=0;i<stat;i++)
 53         {
 54             int cnt=0;
 55             for(int j=0;j<m-k;j++)
 56                 if(i&(1<<j))
 57                 {
 58                     x[free_x[j]]=1;
 59                     cnt++;
 60                 }
 61                 else
 62                     x[free_x[j]]=0;
 63             for(int j=k-1;j>=0;j--)
 64             {
 65                 int tmp;
 66                 for(tmp=j;tmp<m;tmp++)
 67                     if(a[j][tmp])
 68                         break;
 69                 x[tmp]=a[j][m];
 70                 for(int l=tmp+1;l<m;l++)
 71                     if(a[j][l])
 72                         x[tmp]^=x[l];
 73                 cnt+=x[tmp];
 74             }
 75             if(cnt<ans)
 76                 ans=cnt;
 77         }
 78         return ans;
 79 //    }
 80 //
 81 //    //  唯一解 回代
 82 //    for(int i=m-1;i>=0;i--)
 83 //    {
 84 //        x[i]=a[i][m];
 85 //        for(int j=i+1;j<m;j++)
 86 //            x[i]^=(a[i][j] && x[j]);
 87 //    }
 88 //    int ans=0;
 89 //    for(int i=0;i<n*n;i++)
 90 //        ans+=x[i];
 91 //    return ans;
 92 }
 93 
 94 
 95 void init()
 96 {
 97     memset(a, 0, sizeof(a));
 98     memset(x, 0, sizeof(x));
 99     for(int i=0;i<n;i++)
100         for(int j=0;j<n;j++)
101         {
102             int t=i*n+j;
103             a[t][t]=1;
104             if(i>0)
105                 a[(i-1)*n+j][t]=1;
106             if(i<n-1)
107                 a[(i+1)*n+j][t]=1;
108             if(j>0)
109                 a[i*n+j-1][t]=1;
110             if(j<n-1)
111                 a[i*n+j+1][t]=1;
112         }
113 }
114 
115 int main()
116 {
117     int t;
118     scanf("%d", &t);
119     while(t--)
120     {
121         scanf("%d", &n);
122         init();
123         for(int i=0;i<n;i++)
124             for(int j=0;j<n;j++)
125             {
126                 char ch;
127                 cin>>ch;
128                 a[i*n+j][n*n]=(ch=='w');
129             }
130         int t=Gauss(n*n, n*n);
131         if(t==-1)
132         {
133             printf("inf
");
134             continue ;
135         }
136         printf("%d
", t);
137     }
138     return 0;
139 }
POJ 1681
注意对于无穷解的情况, 初等行变换中的交换会影响判断哪些是自由未知量, 那么就要记录交换