#include<stdio.h>
#include<math.h>
#include<string.h>
#define MaxN 100
#define MaxM 10
#define Total 81*81*9
#define MaxNum(a,b) (a>b?a:b)

int bit[MaxM]={1,3,9,27,81,243,729,2187,6561,19683};
int n,m;
char map[MaxN][MaxM+1];
int tol;
int d2[MaxM],d[MaxM];
int min2[Total],min[Total];
int sit2[Total],sit1[Total];
int ns2,ns1;
int ans,ok=0;

void init()
{ int i,j;
 scanf("%d %d",&n,&m); tol=int(pow(3,m));
 for (i=0,ans=0; i<n; i++) 
 {scanf("%s",map[i]);
  for (j=0; j<m; j++) if (map[i][j]=='H') ok=0;
  if (i%3==0) ans+=4; else ans+=3;
 }
 memset(min2,-1,sizeof(min2));
 memset(min,-1,sizeof(min));
 min2[0]=0; ns2=1; sit2[0]=0;
}

void process(int s,int nc,int c,int base,int sit)
{ int i,tmp=0;
 if (min[sit]==-1) sit1[ns1++]=sit;
 min[sit]=MaxNum(min[sit],nc+base);
 for (i=s; i<m; i++)
  if (d2[i]==0&&map[c][i]=='P')
  {process(i+3,nc+1,c,base,sit+bit[i]*(2-d[i]));
   tmp++; if (tmp>2) break;//贪心 不过还是超时了
  }
}

void search()
{ int i,k;
  int j,tj,tmp;
 for (i=0; i<n; i++)
  {ns1=0;
   for (j=0; j<ns2; j++)
    {for (k=0,tmp=0,tj=sit2[j]; k<m; k++)
      {d2[k]=tj%3; d[k]=MaxNum(d2[k]-1,0); tmp+=bit[k]*d[k]; tj/=3;}
     process(0,0,i,min2[sit2[j]],tmp);
    }
   memcpy(min2,min,sizeof(min));
   memcpy(sit2,sit1,sizeof(sit1));
   ns2=ns1;
   memset(min,-1,sizeof(min));
  }
}

void show()
{ int i;
 for (i=0,ans=0; i<tol; i++) ans=MaxNum(ans,min2[i]);
 printf("%d\n",ans);
}

int main()
{init();
 if (m==10&&ok) printf("%d\n",ans);
 else
 {search();
  show();
 }
 return 0;
}
 
   

• Re:HELP! 为什么会超时呢 我觉得我的代码已经够短小了 :( 谁帮我看看还有什么优化的余地 (42) 11119999 2006-08-28 23:22:10