> #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;
> }

• 对啊，要预处理状态的转移来优化啊（用位表示状态） (0) tzzhwj 2009-05-15 13:17:11