infinity

用16個為存儲棋盤的狀態(tài)，BFS時，每次枚舉所有可能的變換。

Source Code

• Source Code

• #include<stdio.h>
  #include<string.h>
  unsigned int queue[65536],vis[65536],step[65536];
  int main()
  {
      unsigned int i,j,k=1<<15,front=0,rear=0,cnt,tmp;
      queue[++rear]=0;
      for(i=0;i<4;i++)
      {
          for(j=0;j<4;j++)
          {    
              queue[rear]+=(getchar()=='b')*k;
              k>>=1;
          }
          getchar();
      }
      if(queue[rear]==0||queue[rear]==65535) {printf("0\n");return 0;}
      step[queue[rear]]=0;
      memset(vis,0,sizeof(vis[0]));
      vis[queue[rear]]=1;
      while(front<rear)
      {
          cnt=queue[++front];
          for(i=0;i<4;i++)
              for(j=0;j<4;j++)
              {   
                  tmp=cnt;
                  if(i==0)  tmp^=0x1<<(11-4*i-j);
                  else if(i==3)  tmp^=0x1<<(19-4*i-j);
                  else {tmp^=0x1<<(19-4*i-j);tmp^=0x1<<(11-4*i-j);}
                  if(j==0)  tmp^=0x3<<(14-4*i);   
                  else if(j==3)  tmp^=0x3<<(12-4*i);
                  else tmp^=0x7<<(14-4*i-j);    
                  if(tmp==0||tmp==65535) {printf("%d\n",step[cnt]+1); return 0;}
                  else if(!vis[tmp])
                  {queue[++rear]=tmp; step[tmp]=step[cnt]+1;vis[tmp]=1;}
              }
      }   
      printf("Impossible\n");
      return 0;
  }