usaco_3_3_3_camelot.cpp

usaco自己做的1到5章的代码

/*
TASK:camelot
LANG:C
无耻的抄标程……
*/


#include <stdio.h>
#include <stdlib.h>
FILE *fin,*fout;
int xmax,ymax;
int f[27][31][27][31]={0};
int walk[8][2]={{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{1,-2},{-1,2},{-1,-2}};
int walk2[8][2]={{-1,1},{-1,0},{-1,-1},{0,1},{0,-1},{1,1},{1,0},{1,-1}};
int fking(int x1,int y1,int x2,int y2)
{
int t1,t2;
if (x1>x2)t1=x1-x2;else t1=x2-x1;
if(y1>y2)t2=y1-y2;else t2=y2-y1;
if (t1>t2)return t1;else return t2;
}
void fknight(int x,int y,int f[][31])
{int head,tail;
struct qq
{
int x;
int y ;
int s;
}queue[837];
int nx,ny,xx,yy,step,i;
char h[27][31]={0};
h[x][y]=1;
head=0;tail=1;
queue[1].x=x;
queue[1].y=y;
queue[1].s=0;
while (head<tail)
{
   head++;
   nx=queue[head].x;
   ny=queue[head].y;
   step=queue[head].s;
   for(i=0;i<8;i++)
   {
    xx=nx+walk[i][0];
            yy=ny+walk[i][1];
    if (xx>0&&xx<=xmax&&yy>0&&yy<=ymax&&h[xx][yy]==0)
    {
     h[xx][yy]++;
     f[xx][yy]=queue[head].s+1;
     tail++;
     queue[tail].x=xx;
     queue[tail].y=yy;
     queue[tail].s=f[xx][yy];
    // fprintf(fout,"tail=%d x=%dy=%d\n",tail,xx,yy);
    }
   }
}
// fprintf(fout,"tail=%d\n\n",tail);
}

void main()
{
int s,i,j,tot;
struct fighter
{
       int x;
    int y;
} k[781],q[10];
int len;

int smin;
int xx,yy,m;
int d;
int kx,ky,sum,add;
    char tch; 
int flag;
fin=fopen("camelot.in","r");
fout=fopen("camelot.out","w");
fscanf(fin,"%d%d\n",&ymax,&xmax);
tot=0;
while(!feof(fin))
{
   tch=fgetc(fin);
   //putchar(tch);
   while((tch<65||tch>90)&&!feof(fin))
    tch=fgetc(fin);
   if(feof(fin))break;
        k[tot].x=tch-64;
   fscanf(fin,"%d",&tch);
   k[tot].y=tch;
   tot++;
}
tot--;
if (tot==0)
{
   fprintf(fout,"%d\n",0);
}
else
{
        for(i=1;i<=xmax;i++)
    for(j=1;j<=ymax;j++)
     fknight(i,j,f[i][j]);//算出点对点的最短距离
     kx=k[0].x;
     ky=k[0].y;
     len=0;
         for(i=1;i<=9;i++)
   {
    xx=kx+walk2[i][0];
    yy=ky+walk2[i][1];
    if(xx>0&&xx<=xmax&&yy>0&&yy<ymax+1)
    {
     len++;
     q[len].x=xx;
     q[len].y=yy;
    }//枚举King周围的点作为相会点
   }
   len++;
   q[len].x=kx;
   q[len].y=ky;
   smin=0Xffff;
        for(i=1;i<=xmax;i++)
    for(j=1;j<=ymax;j++)

    {
     flag=0;
      for(s=1;s<=tot;s++)
    {
     if (f[k[s].x][k[s].y][i][j]==0&&!(k[s].x==i&&k[s].y==j) )
     {
      flag++;
      break;
     }
    }
    if(flag)continue;
     sum=0;
    for(s=1;s<=tot;s++)
      sum+=f[k[s].x][k[s].y][i][j];
    sum+=fking(kx,ky,i,j);
    add=0Xffff;
    for(m=1;m<=len;m++) 
             for(s=1;s<=tot;s++)
    {
     if (f[ k[s].x ][ k[s].y ][q[m].x ][q[m].y]==0&&!(k[s].x==q[m].x&&k[s].y==q[m].y ))
      continue;
     d=f[ k[s].x ][ k[s].y ][q[m].x ][q[m].y]+
      f[q[m].x][q[m].y][i][j]+1;
     if (m==len)d--;
     d=d-fking(kx,ky,i,j)-f[k[s].x][k[s].y][i][j];
     if(d<add)add=d;
    }
    if (add<0)sum+=add;
              if (sum<smin)smin=sum;
    }
fprintf(fout,"%d\n",smin);
}
fclose(fin);
fclose(fout);
exit(0);
}