题意：翻转某些牌 使得达到目标状态
BFS+位运算
因为整个图比较小，所以用位运算来记录状态。
View Code
1 #include<stdio.h> 2 #include<stdlib.h> 3 #include<string.h> 4 #include<queue> 5 using namespace std; 6 const int inf = 0x7fffffff; 7 const int maxn = 16; 8 const int maxm = 65535; 9 int vis[ maxm+5 ]; 10 int dis[ maxm+5 ]; 11 int mat[ maxn ][ maxn ]; 12 int bina[]={1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768}; 13 int cc[16]={19,39,78,140,305,626,1252,2248,4880,10016,20032,35968,12544,29184,58368,51200}; 14 int main( int argc,char argv[] ){ 15 char a[ maxn ]; 16 int sum=0; 17 for( int i=0;i<4;i++ ){ 18 scanf("%s",a); 19 for( int j=0;j<4;j++ ){ 20 if( a[j]=='b' ){ 21 mat[i][j]=1; 22 } 23 else{ 24 mat[i][j]=0; 25 } 26 sum+=(bina[4*i+j]*mat[i][j]); 27 } 28 } 29 memset( vis,0,sizeof(vis) ); 30 for( int i=0;i<=maxm;i++ ) 31 dis[ i ]=inf; 32 if( sum==0||sum==maxm ){ 33 vis[ sum ]=1; 34 dis[ sum ]=0; 35 } 36 queue<int>q; 37 vis[ sum ]=1; 38 dis[ sum ]=0; 39 q.push( sum ); 40 while( !q.empty() ){ 41 int now=q.front(); 42 q.pop(); 43 if( now==0||now==maxm ){ 44 vis[ now ]=1; 45 break; 46 } 47 if( vis[0]||vis[ maxm ] ){ 48 break; 49 } 50 for( int i=0;i<16;i++ ){ 51 int next=now^cc[i]; 52 if( vis[ next ]==0 ){ 53 vis[ next ]=1; 54 dis[ next ]=dis[ now ]+1; 55 q.push( next ); 56 } 57 else{ 58 if( dis[ next ]>dis[ now ]+1 ){ 59 dis[ next ]=dis[ now ]+1; 60 } 61 } 62 } 63 } 64 if( vis[ 0 ]==1 ||vis[ maxm ]==1 ){ 65 printf("%d\n",min( dis[0],dis[ maxm ] ) ); 66 } 67 else 68 { 69 printf("Impossible\n"); 70 } 71 return 0; 72 }