POJ 1681 (开关问题+高斯消元法)

时间：2022-05-30 18:28:07

题目链接: http://poj.org/problem?id=1681

题目大意：一堆格子，或白或黄。每次可以把一个改变一个格子颜色，其上下左右四个格子颜色也改变。问最后使格子全部变黄，最少需要改变几个格子。

解题思路：

与POJ 1222类似。

一共只有15*15个格子，设初始解向量黄为0，白为1.

对于每个开关，设其改变状态为x5，上下左右四个开关改变状态分别为x1,x2,x3,x4,

那么有方程x1^x2^x3^x4^x5^初始状态=0。

这样就有15*15个方程。解这15*15个线性方程组，就能得到每个格子的改变状态。

注意这里高斯消元的是一个开关矩阵，而不是黄白矩阵，也就是说，如果最后的解为0，不是表示这个格子为黄，而是这个格子相对于初始状态没有改变。

那么问题就来了，如何知道改变的最少格子？

其实很简单，在得到最终改变格子的状态后，统计一下里面的改变的格子数，也就是解为1的元，就是结果。

同时由于要判断无解情况，所以不能使用POJ 1222中那样的简略写法。

#include "cstdio"

#include "iostream"

#include "cstring"

using namespace std;

int ratio[][],dir[][]={,,-,,,,,-,,},T,n;

void reset()

{

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

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

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

    {

        int x=i+dir[k][],y=j+dir[k][];

        if(x>=&&y>=&&x<n&&y<n) ratio[i*n+j][x*n+y]=;

    }

}

bool gauss()

{

    int i,j,k;

    for(i=,j=;i<n*n&&j<n*n;i++,j++)

    {

        k=i;

        for(;k<n*n;k++)

           if(ratio[k][j]) break;

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

            if(i!=k) swap(ratio[i][t],ratio[k][t]);

        if(!ratio[i][j]) {i--;continue;}

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

        {

            if(ratio[k][j])

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

                   ratio[k][t]^=ratio[i][t];

        }

    }

    k=i;

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

        if(ratio[i][n*n]) return false;

    for(i=k-; i>=; i--)

    {

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

            ratio[i][n*n]^=(ratio[i][j]&ratio[j][n*n]);

    }

    return true;

}

int main()

{

    //freopen("in.txt","r",stdin);

    char c;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        memset(ratio,,sizeof(ratio));

        reset();

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

        {

            scanf(" %c",&c);

            if(c=='w') ratio[i][n*n]=;

            if(c=='y') ratio[i][n*n]=;

        }

        int ans=gauss();

        if(!ans) printf("inf\n");

        else

        {

            int ans=;

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

                if(ratio[i][n*n]==) ans++;

            printf("%d\n",ans);

        }

    }

}
13597338 neopenx 1681 Accepted 364K 16MS C++ 1651B 2014-11-04 13:14:49

相关文章