POJ1681 Painter's Problem（高斯消元）

题目看似与线性方程组无关，但可以通过建模转化为线性方程组的问题。

对于一块砖，刷两次是没有必要的，我们令x=1表示刷了一次，x=0没有刷，一共有n*n个，所以相当于有n*n个未知量x。

定义aij表示i和j的关系，是邻居则为1，否则是0；我们又用0表示黄色，1表示白色，一个方格最后的颜色，取决于它的初始颜色和所有他的邻居格子的异或操作情况。

就可以得到n*n个方程，a为系数，x为变量，每个方程的含义就是代表每个格子与邻居格子异或之后为0（黄色）。

x=1，表示这个格子被刷了一次，统计所有x=1的数量就是答案。

 1 #include<cstdio>

 2 #include<iostream>

 3 #include<cstring>

 4 using namespace std;

 5 int a[230][230],d[5][2]={{0,0},{-1,0},{1,0},{0,-1},{0,1}};

 6 int T,n;

 7

 8 bool gauss(){

 9     int r,c;

10     for(r=0,c=0;c<n*n;c++){

11         int t=r;

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

13             if(a[i][c]){t=i;break;}

14         if(!a[t][c]) continue;

15         for(int i=c;i<=n*n;i++) swap(a[t][i],a[r][i]);

16         for(int i=r+1;i<n*n;i++)

17             if(a[i][c])

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

19                     a[i][j]^=a[r][j];

20         r++;

21     }

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

23             if(a[i][n*n]) return false;

24     for(int i=n*n-1;i>=0;i--)

25         for(int j=i+1;j<n*n;j++)

26             a[i][n*n]^=a[i][j]&a[j][n*n];

27     return true;

28 }

29

30 int main(){

31     char c;

32     scanf("%d",&T);

33     while(T--){

34         scanf("%d",&n);

35         memset(a,0,sizeof(a));

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

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

38                 for(int k=0;k<5;k++){

39                     int x=i+d[k][0],y=j+d[k][1];

40                     if(x>=0&&y>=0&&x<n&&y<n)

41                         a[i*n+j][x*n+y]=1;

42                 }

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

44             scanf(" %c",&c);

45             if(c=='w') a[i][n*n]=1;

46             if(c=='y') a[i][n*n]=0;

47         }

48         int ans=gauss();

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

50         else{

51             int ans=0;

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

53                 if(a[i][n*n]==1) ans++;

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

55         }

56     }

57 }

巴特西

POJ1681 Painter's Problem（高斯消元）

最新文章

热门文章