1 /* 2 题意：n行m列的矩阵，1表示可以放东西，0表示不可以。曼哈顿距离为2的两个位置最多只能有一个位置放东西。 3 问最多放多少个东西。 4 */ 5 #include<stdio.h> 6 #include<string.h> 7 #include<stdlib.h> 8 #include<algorithm> 9 #include<iostream> 10 #include<queue> 11 #include<stack> 12 #include<math.h> 13 #include<map> 14 using namespace std; 15 const int maxn = 105; 16 const int maxm = 12; 17 const int N = 170; 18 int mat[ maxn ]; 19 int dp[ maxn ][ N ][ N ]; 20 int state[ N ]; 21 int ones_state[ N ]; 22 int Count_ones( int x ){ 23 int cnt = 0; 24 while( x ){ 25 if( x&1 ) 26 cnt++; 27 x>>=1; 28 } 29 return cnt; 30 } 31 int init( int n,int m ){ 32 memset( state,0,sizeof( state ) ); 33 memset( ones_state,0,sizeof( state ) ); 34 int M = 1<<m; 35 int cnt = 0; 36 for( int i=0;i<M;i++ ){ 37 if( (i&(i<<2))==0&&(i&(i>>2))==0 ){ 38 state[ cnt ] = i; 39 ones_state[ cnt ] = Count_ones( i ); 40 cnt++; 41 } 42 } 43 //printf("cnt=%d ",cnt);最多169种状态！！ 44 return cnt; 45 } 46 void DP( int cnt,int n,int m ){ 47 memset( dp,-1,sizeof( dp ) ); 48 for( int i=0;i<cnt;i++ ){ 49 if( (state[i]&mat[0])==0 ) 50 dp[0][i][0] = ones_state[ i ]; 51 }//初始化 52 for( int i=1;i<n;i++ ){ 53 for( int j=0;j<cnt;j++ ){ 54 if( (state[j]&mat[i])==0 ){ 55 for( int k=0;k<cnt;k++ ){ 56 if( (state[j]&(state[k]<<1))==0&&(state[j]&(state[k]>>1))==0 ){ 57 for( int k2=0;k2<cnt;k2++ ){ 58 if( dp[i-1][k][k2]==-1 ) continue; 59 if( (state[j]&state[k2])==0&&(state[k]&(state[k2]>>1))==0&&(state[k]&(state[k2]<<1))==0 ) 60 dp[ i ][ j ][ k ] = max( dp[i][j][k],dp[i-1][k][k2]+ones_state[j] ); 61 } 62 } 63 } 64 } 65 } 66 } 67 } 68 int main(){ 69 int n,m; 70 while( scanf("%d%d",&n,&m)==2 ){ 71 int cnt = init( n,m ); 72 memset( mat,0,sizeof( mat ) ); 73 int tmp; 74 for( int i=0;i<n;i++ ){ 75 for( int j=0;j<m;j++ ){ 76 scanf("%d",&tmp); 77 if( tmp==0 ){ 78 mat[ i ] |= (1<<j); 79 } 80 } 81 } 82 DP( cnt,n,m ); 83 int ans = 0; 84 for( int i=0;i<cnt;i++ ) 85 for( int j=0;j<cnt;j++ ) 86 ans = max( ans,dp[n-1][i][j]); 87 printf("%d ",ans); 88 } 89 return 0; 90 }