[Gauss]POJ1222 EXTENDED LIGHTS OUT

题意：给一个5*6的矩阵

1代表该位置的灯亮着， 0代表该位置的灯没亮

按某个位置的开关，可以同时改变该位置以及该位置上方、下方、左方、右方，共五个位置的灯的开、关（1->0, 0->1）

问能否将所有的灯关闭若能输出需要按哪些地方；不能输出-1

高斯消元的入门题。

每个位置可以列出一个方程，列出增广矩阵：

　　每个位置可以形成增广矩阵的一行，每行都有30个系数分别代表（0到29号灯），将 可以影响该位置改变的 位置（自己、上、下、左、右）对应的置1，其余置0

　　这样就形成了30*30的系数矩阵。

　　将初始状态置入最后一列就形成了增广矩阵

接下来只要解方程组即可。

化成约化阶梯后最后一列即为该方程组的解。

P.s. 需要注意的是：因为是矩阵表示的是灯的开关状态，所以解的过程中不应出现0、1以外的其余数字即 01方程用异或求解

 int a[][];  // 增广矩阵

 int x[];  // 解

 int free_x[]; // 标记是否为自由未知量

 int n, m;

 void debug()

 {

     for(int i=;i<n*n;i++)

     {

         for(int j=;j<n*n;j++)

             printf("%d ", a[i][j]);

         printf("\n");

     }

 }

 void Gauss(int n, int m) // n个方程 m个未知数 即 n行m+1列

 {

     //转换为阶梯形式

     int col=, k, num=;

     for(k=;k<n && col<m;k++, col++)

     {//枚举行

         int max_r=k;

         for(int i=k+;i<n;i++)//找到第col列元素绝对值最大的那行与第k行交换

             if(abs(a[i][col])>abs(a[max_r][col]))

                 max_r=i;

         if(max_r!=k)// 与第k行交换

             for(int j=col;j<m+;j++)

                 swap(a[k][j], a[max_r][j]);

         if(!a[k][col])// 说明该col列第k行以下全是0了

         {

             k--;

             free_x[num++]=col;

             continue;

         }

         for(int i=k+;i<n;i++)// 枚举要删除的行

             if(a[i][col])

                 for(int j=col;j<m+;j++)

                     a[i][j]^=a[k][j];

     }

 //    debug();

 //    printf("%d %d\n", col, k);

 //

 //    for(int i=k;i<n;i++)

 //        if(a[i][col])

 //            return -1; // 无解

 //    if(k<m)   //m-k为自由未知量个数

 //    {

 //        int stat=1<<(m-k);

 //        int ans=INT_MAX;

 //        for(int i=0;i<stat;i++)

 //        {

 //            int cnt=0;

 //            for(int j=0;j<m-k;j++)

 //                if(i&(1<<j))

 //                {

 //                    x[free_x[j]]=1;

 //                    cnt++;

 //                }

 //                else

 //                    x[free_x[j]]=0;

 //            for(int j=k-1;j>=0;j--)

 //            {

 //                int tmp;

 //                for(tmp=j;tmp<m;tmp++)

 //                    if(a[j][tmp])

 //                        break;

 //                x[tmp]=a[j][m];

 //                for(int l=tmp+1;l<m;l++)

 //                    if(a[j][l])

 //                        x[tmp]^=x[l];

 //                cnt+=x[tmp];

 //            }

 //            if(cnt<ans)

 //                ans=cnt;

 //        }

 //        return ans;

 //    }

 //

     //  唯一解 回代

     for(int i=m-;i>=;i--)

     {

         x[i]=a[i][m];

         for(int j=i+;j<m;j++)

             x[i]^=(a[i][j] && x[j]);

     }

 //    int ans=0;

 //    for(int i=0;i<n*n;i++)

 //        ans+=x[i];

 //    return ans;

 }

 void init()

 {

     n=, m=;

     memset(a, , sizeof(a));

     memset(x, , sizeof(x));

     for(int i=;i<n;i++)

         for(int j=;j<m;j++)

         {

             int t=i*m+j;

             a[t][t]=;

             if(i>)

                 a[(i-)*m+j][t]=;

             if(i<n-)

                 a[(i+)*m+j][t]=;

             if(j>)

                 a[i*m+j-][t]=;

             if(j<m-)

                 a[i*m+j+][t]=;

         }

 }

 int main()

 {

     int t, ca=;

     scanf("%d", &t);

     while(t--)

     {

         init();

         for(int i=;i<n*m;i++)

             scanf("%d", &a[i][n*m]);

         printf("PUZZLE #%d\n", ca++);

         Gauss(n*m, n*m);

         for(int i=;i<n;i++)

             for(int j=;j<m;j++)

             {

                 printf("%d", x[i*m+j]);

                 if(j==)

                     printf("\n");

                 else

                     printf(" ");

             }

     }

     return ;

 }

POJ 1222

巴特西

[Gauss]POJ1222 EXTENDED LIGHTS OUT

最新文章

热门文章