#include <stdio.h>
#include <string.h>
#define MAXN 131100
int mat[MAXN];
int queue[MAXN];
int father[MAXN];
int path[MAXN];
int op[MAXN];
int main()
{
   char map[6][6];
   int t,count,top,tmp,i,j,k,p,f;
   t=0;
   count=0;
   for(i=0;i<4;i++)
   {
      scanf("%s",map[i]);
      for(j=0;j<4;j++)
      {
         if(map[i][j]=='+') t+=(1<<count);
         count++;
      }
   }
   if(t==0) printf("0\n");
   else
   {
      top=0;
      queue[0]=t;
      father[0]=-1;
      memset(mat,0,sizeof(mat));
      mat[t]=1;
      f=0;
      for(i=0;i<=top;i++)
      {
         for(j=0;j<4;j++)
         {
            for(k=0;k<4;k++)
            {
               tmp=queue[i];
               for(p=j*4;p<j*4+4;p++) tmp^=(1<<p);
               for(p=k;p<16;p+=4)
               {
                  if(p/4==j) continue;
                  tmp^=(1<<p);
               }
               if(!mat[tmp])
               {
                  top++;
                  queue[top]=tmp;
                  father[top]=i;
                  path[top]=j*4+k;
                  mat[tmp]=1;
                  if(tmp==0) f=1;
               }
               if(f) break;
            }
            if(f) break;
         }
         if(f) break;
      }
      count=-1;
      while(top>0)
      {
         count++;
         op[count]=path[top];
         top=father[top];
      }
      printf("%d\n",count+1);
      for(i=count;i>=0;i--) printf("%d %d\n",op[i]/4+1,op[i]%4+1);
   }
   //while(1);
   return 0;
}

• 睡醒来才发现原来那16种操作可以提前存起来，差别居然这么大！汗．．． (1702) nuanran 2006-08-15 10:20:27
  • 对啊，要预处理状态的转移来优化啊（用位表示状态） (0) tzzhwj 2009-05-15 13:17:11