POJ_1222_高斯消元

题目描述：

　　每组数据给出一个5*6的0 1矩阵，每次操作可以把某个位置及其四周的位置0 1置换，要求输出操作位置的矩阵。

思路：

　　每个位置操作2次则等于没有操作，所以每个位置有操作和不操作两种选择，爆搜应该会超时。

　　在网上看到了高斯消元的做法，按照每个操作位置影响的位置构造系数矩阵，然后读入题目的数据构成增广矩阵。

　　接下来的做法便和高斯消元一样，只是把原来的-变成了^。

　　30条方程，30个未知量，所以最终的解也是唯一。

#include<cstdio>

#include<iostream>

using namespace std;

int a[][] = {};

int main()

{

    int n;

    cin >> n;

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

    {

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

        {

            a[i][i] = ;

            if(i > )   a[i][i-] = ;

            if(i < )  a[i][i+] = ;

            if(i%)     a[i][i-] = ;

            if((i+)%) a[i][i+] = ;

        }

        for(int i = ;i < ;i++)   cin >> a[i][];

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

        {

            int temp = i;

            for(;temp < ;temp++)

            {

                if(a[temp][i])

                {

                    for(int j = ;j <= ;j++)  swap(a[temp][j],a[i][j]);

                    break;

                }

            }

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

            {

                if(j != i && a[j][i])

                {

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

                    {

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

                    }

                }

            }

        }

        cout << "PUZZLE #" << x << endl;

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

        {

            if((i+)%) cout << a[i][] << " ";

            else        cout << a[i][] << endl;

        }

    }

    return ;

}

巴特西

POJ_1222_高斯消元

最新文章

热门文章