holedox.cpp

2002年ACM Asia-BeiJing的比赛题目及原创算法解决方案：Holedox Moving

#include <fstream.h>

int n,m,L,K;
int stepnum;
int shortest;
int stepx[200],stepy[200],stepi[200],stepj[200];
int pstep;
   int cur[21][21];
   int bodyx[10],bodyy[10];

void copy(int cur[][21],int pre[][21]){
   for(int i=1;i<n;i++)
      for(int j=1;j<m;j++)
         pre[i][j]=cur[i][j];
}

void copyb(int body[],int prebody[]){
   for(int i=0;i<L;i++)
      prebody[i]=body[i];
}

int search(int headx,int heady,int i,int j){
   for(int m=0;m<pstep;m++){
      if(headx==stepx[m]&&heady==stepy[m]&&i==stepi[m]&&j==stepj[m]) return 1 ;
   }
   return 0;
}

int move(int i,int j){
   if(bodyx[0]+i>=1&&bodyx[0]+i<=n&&bodyy[0]+j>=1&&bodyy[0]+j<=m&&cur[bodyx[0]+i][bodyy[0]+j]==0){
      if(search(bodyx[0],bodyy[0],i,j)) return 0;
      cur[bodyx[L-1]][bodyy[L-1]]=0;
      for(int n=L-1;n>=1;n--){
         bodyx[n]=bodyx[n-1];bodyy[n]=bodyy[n-1];
      }
      bodyx[0]+=i;bodyy[0]+=j;
      cur[bodyx[0]][bodyy[0]]=1;
      return 1;
   }
   else return 0;
}

void run(){
   int pre[21][21];
   int prebodyx[10],prebodyy[10];
   if(bodyx[0]==1&&bodyy[0]==1){
      if(shortest==-1||shortest>stepnum) shortest=stepnum;
      return;
   }
   copy(cur,pre);
   copyb(bodyx,prebodyx);
   copyb(bodyy,prebodyy);
   stepx[pstep]=bodyx[0];
   stepy[pstep]=bodyy[0];
   if(move(-1,0)){
      stepnum++;
      stepi[pstep]=-1;
      stepj[pstep]=0;
      pstep++;
      run();
      copy(pre,cur);copyb(prebodyx,bodyx);copyb(prebodyy,bodyy);
      stepnum--;
      pstep--;
   }
   if(move(1,0)){
      stepnum++;
      stepi[pstep]=1;
      stepj[pstep]=0;
      pstep++;
      run();
      copy(pre,cur);copyb(prebodyx,bodyx);copyb(prebodyy,bodyy);
      stepnum--;
      pstep--;
   }
   if(move(0,-1)){
      stepnum++;
      stepi[pstep]=0;
      stepj[pstep]=-1;
      pstep++;
      run();
      copy(pre,cur);copyb(prebodyx,bodyx);copyb(prebodyy,bodyy);
      stepnum--;
      pstep--;
   }
   if(move(0,1)){
      stepnum++;
      stepi[pstep]=0;
      stepj[pstep]=1;
      pstep++;
      run();
      copy(pre,cur);copyb(prebodyx,bodyx);copyb(prebodyy,bodyy);
      stepnum--;
      pstep--;
   }

}

void init(ifstream &fin){
   int i,j;
   for(i=1;i<=n;i++)
      for(j=1;j<=m;j++)
         cur[i][j]=0;
      for(i=0;i<L;i++){
         fin>>bodyx[i]>>bodyy[i];
         cur[bodyx[i]][bodyy[i]]=1;
      }
      fin>>K;
      for(i=0;i<K;i++){
         int tx,ty;
         fin>>tx>>ty;
         cur[tx][ty]=2;
      }
}

int main(){
   ifstream fin;
   fin.open("holedox.in");

   int i,j;
   int casenum=1;
   fin>>n>>m>>L;
   while(n!=0&&m!=0&&L!=0){
      stepnum=0;
      shortest=-1;
      init(fin);

      pstep=0;

      run();

      cout<<"Case "<<casenum++<<": "<<shortest<<endl;
      fin>>n>>m>>L;
   }

   fin.close();
   cin>>i;
   return 1;
}