poj1681 Painter's Problem

リンクhttp://poj.org/problem?id=1681


View Code

 1 #include <stdio.h> 

 2 #include <string.h>

 3 #include <algorithm>

 4 #include <cmath>

 5 using namespace std;

 6 int d[230][230], N, M;

 7 char s[16][16]; 

 8 void solve( int n)

 9 {

10     int x[230],m[20], t, ans=1000, temp;

11     t=M-n;

12     for( int i=1; i<=pow( 2, t ); ++i ){

13         memset( x, 0, sizeof x  );

14         for(int j=0; j<t; ++j){

15             m[j]=(i&(1<<j));

16             if(m[j]){

17                 x[n+j]=1;

18             }    

19         }

20         temp=0;

21         for( int p=n+1;p>=1;--p ){

22             for(int k=i+1;k<=M;++k){

23                     x[p]^=( x[k]&&d[p][k] );

24                 

25             }

26             x[p]^=d[p][M+1];

27             if( x[p])

28                 temp++;

29         } 

30         ans=min( ans, temp );

31     }

32     printf( "%d
", ans );

33 }

34 void Gauss(  )

35 {

36     int i=1, j, k , p, t;

37     for(j=1; j<=M; ++j){

38         for(p=i; p<=M; ++p){

39             if(d[p][j])break;

40         }

41         if( p>M )continue;

42         if(p!=i){

43             for(k=j;k<=M+1; ++k){

44                 t=d[p][k],d[p][k]=d[i][k],d[i][k]=t;

45             }    

46         }

47         for(p=i+1; p<=M; ++p){

48             if( d[p][j] ){

49                 for( k=j; k<=M+1; ++k ){

50                     d[p][k]^=d[i][k];

51                 }

52             }

53         }

54         ++i;

55     }

56     for( p=i; p<=M; ++p ){

57         if( d[p][M+1] ){

58             puts("inf");

59             return;

60         }

61     }    

62     solve( i-1 );

63 }

64 int main( )

65 {

66     int T; 

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

68     while( T --) {

69         scanf( "%d", &N );

70         M=N*N;

71         for( int i=0; i<N; ++ i ){

72             scanf( "%s", s[i] ); 

73         } 

74         memset( d, 0, sizeof d );

75         for( int i=1; i<=M; ++ i )

76             d[i][i]=1;

77         for( int i=0; i<N; ++i ){

78             for( int j=0;j<N; ++j ){

79                 if( s[i][j]=='w' ) d[i*N+j+1][M+1]=1;

80                 

81                 if( i>0 )d[(i-1)*N+j+1][i*N+j+1]=1;

82                 if( j>0 )d[i*N+j][i*N+j+1]=1;

83                 if( i<N-1 )d[(i+1)*N+j+1][i*N+j+1]=1;

84                 if( j<N-1 )d[i*N+j+2][i*N+j+1]=1;        

85             } 

86         }

87         Gauss( ); /*

88         for( int i=1; i<=M; ++i ){

89             for(int j=1;j<=M; ++ j ){

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

91             }

92             puts( "" );

93         }*/

94     } 

95     return 0;    

96 }