xfstart07
Get busy living or get busy dying

#include < iostream >
using   namespace  std;

int  a[ 5 ][ 5 ];
const   int  d[ 5 ][ 2 ] = { 0 , 0 , - 1 , 0 , 0 , - 1 , 1 , 0 , 0 , 1 };
int  Min;
bool  check(){
    
for ( int  i = 0 ;i < 4 ; ++ i)
        
for ( int  j = 0 ;j < 4 ; ++ j)
            
if (a[i][j] != a[ 0 ][ 0 ])
                
return   0 ;
    
return   1 ;
}
void  dfs( int  x, int  y, int  num){
    
if (num >= Min)  return ;
    
if (y == 4 ){
        x
++ ; y = 0 ;
    }
    
if (check()){
        
if (Min > num)
            Min
= num;
        
return ;
    }
    
if (x == 4 return ;
    dfs(x,y
+ 1 ,num);
    
for ( int  i = 0 ;i < 5 ; ++ i){
        
int  ax = x + d[i][ 0 ],bx = y + d[i][ 1 ];
        
if (ax < 0 || ax > 3 || bx < 0 || bx > 3 continue ;
        a[ax][bx]
= 1 - a[ax][bx];
    }
    dfs(x,y
+ 1 ,num + 1 );
    
for ( int  i = 0 ;i < 5 ; ++ i){
        
int  ax = x + d[i][ 0 ],bx = y + d[i][ 1 ];
        
if (ax < 0 || ax > 3 || bx < 0 || bx > 3 continue ;
        a[ax][bx]
= 1 - a[ax][bx];
    }
}
int  main()
{
    
char  c;
    
for ( int  i = 0 ;i < 4 ; ++ i){
        
for ( int  j = 0 ;j < 4 ; ++ j){
            c
= getchar();
            
if (c == ' b ' ) a[i][j] = 1 ;
            
else  a[i][j] = 0 ;
        }
        getchar();
    }
    Min
= 0xFFFFFFF ;
    dfs(
0 , 0 , 0 );
    
if (Min == 0xFFFFFFF )
        printf(
" Impossible\n " );
    
else  printf( " %d\n " ,Min);
    
return   0 ;
}



posted on 2009-05-28 16:40 xfstart07 阅读(131) 评论(0)  编辑 收藏 引用 所属分类: 代码库

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理