Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

调试了2天终于...犯尽了各种错误...

Posted by ACM_Micro_C at 2009-05-30 15:30:46 on Problem 1178
```#include <iostream>
#include <string.h>
#include <cmath>
#include <stdlib.h>
using namespace std;

const int MAX=0x7fffffff/2;
char str[200];
int king[1][2];
int dis[65][65], disking[65][65];
int knight[65][2];int numknight;
const int str1[]={-2,-2,-1,-1,1,1,2,2},str2[]={-1,1,-2,2,-2,2,-1,1};

bool legal(int x,int y)
{
return (x>=1&&x<=8&&y>=1&&y<=8);
}
void floyed()
{
int i,j,k;
for(k=1;k<=64;k++)
for(i=1;i<=64;i++)
for(j=1;j<=64;j++)
if(dis[i][k]+dis[k][j]<dis[i][j]) dis[i][j]=dis[i][k]+dis[k][j];

for(k=1;k<=64;k++)
for(i=1;i<=64;i++)
for(j=1;j<=64;j++)
if(disking[i][k]+disking[k][j]<disking[i][j]) disking[i][j]=disking[i][k]+disking[k][j];
}
void inition()
{
int i,j,k,u;
for(i=1;i<=64;i++)
for(j=1;j<=64;j++)
if(i==j)
{dis[i][j]=0;disking[i][j]=0;}
else
{
dis[i][j]=MAX;
dis[j][i]=MAX;
disking[i][j]=MAX;
disking[j][i]=MAX;
}
for(i=1;i<=64;i++)
{
int x=i/8+1,y=i-i/8*8;if(i%8==0)x--;if(y==0) y=8;
for(j=0;j<8;j++)
if(legal(x+str1[j],y+str2[j]))
{
dis[(x-1)*8+y ][ (x+str1[j]-1)*8+y+str2[j]]=1;
dis[ (x+str1[j]-1)*8+y+str2[j]][(x-1)*8+y ]=1;
}
for(k=-1;k<=1;k++)
for(u=-1;u<=1;u++)
if(k==0&&u==0) disking[k][u]=0;
else
{
if(legal(x+k,y+u))
{
disking[i][(x+k-1)*8+y+u]=1;
disking[(x+k-1)*8+y+u][i]=1;
}
}
}
floyed();
}

void f()
{
int i,j,k,u;int ans=MAX;int sum;
for(i=1;i<=64;i++) // node=    i/8+1  , (i-1)%8+1 循环64个可能的目标点。
{
for(j=1;j<=64;j++) //选被选的骑士跟头领的汇合点
{
for(k=1;k<numknight;k++) //选可能带头领的骑士
{
sum=disking[king[0][0]*8-8+king[0][1]][j];
for(u=1;u<numknight;u++)
{
if(u==k)
sum+=dis [knight[u][0]*8-8+knight[u][1]][j] + dis[j][i];
else
sum+=dis[knight[u][0]*8-8+knight[u][1]][i];
}
if(ans>sum) ans=sum;
}
}
}
printf("%d\n",ans);
}
int main()
{
inition();
while(cin>>str)
{
numknight=1;
int len=strlen(str);
if(len==2) {cout<<0<<endl;continue;}
else
{
for(int i=0;i<len;i+=2)
if(i==0){king[0][0]=str[i]-'A'+1;king[0][1]=str[i+1]-'0';}
else {knight[numknight][0]=str[i]-64;knight[numknight][1]=str[i+1]-'0';numknight++;}
f();
}
}
return 0;
}
```

Followed by: