ZJU时限是10S,比PKU的数据强一倍，在PKU470MS AC的程序在ZJU要850MS.
下面是我RE的程序，请高手指点^_^


# include <iostream>
# include <set>
# include <queue>
# include <algorithm>
# include <math.h>
using namespace std;
const int N=20;
const unsigned   r=1;
const unsigned   l=2;
const unsigned   u=3;
const unsigned   d=4;
bool reach;
bool stones[N+2][N+2],cpstones[N+2][N+2]; 
unsigned vst[4]; //扩展的合法状态
int tn=0;
set<unsigned> closed;
struct state{
unsigned seq;
int f; //f(x)=g(x)+h(x)
int g; 
};
int len,TB,row,cow;
int clen;

struct comp //自定义比较的函数
{
bool operator () (state a, state b)
{
  return a.f > b.f;
}
}; 
priority_queue<state, vector<state>, comp> opened; 
bool isTarget(unsigned st){

  st/=TB;
  return st==1;
};
bool isused(unsigned key){
   //判断某个状态是否已扩展过
   return closed.find(key)!=closed.end();  
}
int getDis(unsigned st){
   //计算当前状态到目标状态的曼哈顿距离
   st/=TB;
   int r=-1;
   int t=st%cow;
   if(!t) t=cow-1;
   else r++;
   r+=st/cow;
   return t-1+r;
}
 
void getAllStates(unsigned st){
   //返回状态st的所有合法的可扩展状态sset和个数
   int i,tlen;
   unsigned CTB=TB,dr,head;
   bool dir[4];
   memset(dir,1,sizeof(dir));
   clen=0;
   unsigned tseq,x,y;
   head=st/TB; 
   tseq=st%TB;

   y=head%cow;
   x=head/cow;
   if(!y) y=cow;
   else x++;
  
   
   int sx=x,sy=y;
   tlen=len-1;
   for(i=0;i<tlen;i++){
	  CTB/=10;
      dr=tseq/CTB;
	  dr%=10;
	  if(dr==u){
        sx++;
	  }else if(dr==d){
        sx--;
	  }else if(dr==r){
        sy--;
	  }else{
        sy++;
	  }
	  if(sx==x-1&&sy==y){
         dir[0]=false; 
	  }else if(sx==x+1&&sy==y){
         dir[1]=false; 
	  }else if(sx==x&&sy==y-1){
         dir[2]=false; 
	  }else if(sx==x&&sy==y+1){
         dir[3]=false; 
	  }
   }
   if(dir[0]&&!stones[x-1][y]){
        vst[clen++]=TB*((x-2)*cow+y)+(tseq/10)+u*TB/10;
   }
   if(dir[1]&&!stones[x+1][y]){
        vst[clen++]=TB*(x*cow+y)+(tseq/10)+d*TB/10;
   }
   if(dir[2]&&!stones[x][y-1]){
	   vst[clen++]=TB*((x-1)*cow+y-1)+(tseq/10)+l*TB/10;
   }
   if(dir[3]&&!stones[x][y+1]){
	   vst[clen++]=TB*((x-1)*cow+y+1)+(tseq/10)+r*TB/10;
   }
} 
 

bool Solve(){
	if(!reach) return false;
    state  cs,ns;
	int i;
    while(!opened.empty()){
       cs=opened.top();
       opened.pop();
	   if(isTarget(cs.seq)){
		   printf("Case %d: %d\n",tn,cs.f);
           return true;
		   break;
	   }
	   getAllStates(cs.seq);
	   for(i=0;i<clen;i++){
		   if(!isused(vst[i])){
			   closed.insert(vst[i]);
			   ns.seq=vst[i];
			   ns.g=cs.g+1;
               ns.f=ns.g+getDis(vst[i]); 
			   opened.push(ns);
		   }
	   }
	}
	return false;
}

void dfs(int x,int y){
    cpstones[x][y]=true;
	if(!cpstones[x-1][y]) dfs(x-1,y);
	if(!cpstones[x+1][y]) dfs(x+1,y);
	if(!cpstones[x][y-1]) dfs(x,y-1);
	if(!cpstones[x][y+1]) dfs(x,y+1);
}

bool quick_check(int x,int y){
	//判断可达性(x,y)到(1,1)是否可达
	memcpy(cpstones,stones,sizeof(stones));
    dfs(1,1);
	return cpstones[x][y];
}


int main(){
   unsigned pi,pj,k,i,j,tseq,sn,hi,hj;
   state st;
   while(scanf("%d %d %d",&row,&cow,&len),row+cow+len){
	   reach=true;
	   memset(stones,0,sizeof(stones));
	   while(!opened.empty()) opened.pop();
	   closed.clear();
	   TB=pow(10.0,len-1);
       scanf("%d %d",&pi,&pj);   
	   hi=pi;
	   hj=pj;
	   st.seq =cow*(pi-1)+pj;
	   st.seq*=TB;
	   tseq=0;
	   for(k=1;k<len;k++){
       scanf("%d %d",&i,&j);
       if(pi-i==1){
       tseq+=d;
	   }else if(i-pi==1){
       tseq+=u; 
	   }else if(pj-j==1){
       tseq+=r;
	   }else{
       tseq+=l;   
	   }
	   tseq*=10;
	   pi=i;pj=j;
	   }
	   tseq/=10;
	   st.seq+=tseq;
	   st.f = getDis(st.seq);
	   st.g = 0;
       opened.push(st);
	   closed.insert(st.seq);
       scanf("%d",&sn);
	   while(sn--){
         scanf("%d %d",&i,&j);
         stones[i][j]=true;
	   }
	   for(i=0;i<=row+1;i++){
		   stones[i][0]=stones[i][cow+1]=true;
	   }
	   for(i=0;i<=cow+1;i++){
		   stones[0][i]=stones[row+1][i]=true;
	   }
	   tn++;
	   if(!quick_check(hi,hj)) reach=false;
	   if(!Solve()) printf("Case %d: -1\n",tn);
   }
   return 1;
}

• Re: 管理员可不可以发几组exin数据？ (0) gzw_02 2008-07-31 09:43:06
• 你这句话不是前后矛盾吗。。。。 (4579) jdx2013519 2009-08-07 18:45:38