我用的是BFS+位运算的判重。
一共会有2^16个状态，每个状态会有16次的转移，每次转移会有10次运算，
所以2^16*16*10=10^7,所以位运算不是O（1）？。。  不解，谢谢。

下面是TLE的代码，希望Cow们帮我分析一下～～ 谢谢
#include<stdio.h>
#include<queue>
#include<cstdlib>
using namespace std;
struct NODE
{
  int sta;       
  int len;
  int num;     
};
void set(int &sta,int x)
{
     sta|=(1<<x);     
}
void flip(int &sta,int x)
{
    sta^=(1<<x); 
}
bool has[(1<<16)];
char s[4];
queue<NODE> q;
int main()
{
  int i,j;
  int sta=0;
  memset(has,0,sizeof(has));
  for(i=0;i<4;i++) 
  {
      scanf("%s",s);                 
      for(j=0;j<4;j++)             
      if(s[j]=='-')
      set(sta,4*i+j);             
  }  
  int ans; NODE node;
  node.sta=sta;node.len=0;node.num=0; has[sta]=1;
  q.push(node);
  while(!q.empty())
  {
     node=q.front();q.pop();                 
     int temp=node.sta;
     int nn,ll;
     nn=node.num;
     ll=node.len;
     if(temp==((1<<16)-1))
     {
      printf("%d\n",ll);         
      for(i=0;i<16;i++) if(nn&(1<<i)) printf("%d %d\n",i/4+1,i%4+1);      
      break;                     
     }        
     
       for(i=0;i<16;i++)
       { 
           if((1<<i)&nn) continue; 
           int kk=temp;  
           flip(kk,i);
           int x,y;
           x=i/4;y=i%4;
           for(j=0;j<4;j++)
           {
           flip(kk,4*x+j);                   
           flip(kk,4*j+y);                
           }      
               if(!has[kk])
               {
               NODE tp;
               has[kk]=1;
               tp.sta=kk;             
               tp.len=ll+1;             
               tp.num=(nn|(1<<i));     
               q.push(tp);        
               }
           
       }
                   
  }
 //system("pause");
 return 0;   
}


PS: G++ 的位运算要比C++的快近一倍？
   

• 我D (2) kamel52045386 2008-07-22 15:58:48