POJ 1178 -- 国王和骑士

国王和骑士

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 3319		Accepted: 1559

题目描述

在一个 8*8 的棋盘里有一个国王和一些骑士，我们要把他们送到同一顶点上去。国王能够选择一名骑士作为坐骑，而与骑士一起行动（相当于一个骑士），同一位置，同一时刻可以有多个骑士。问最少走的步数。骑士的行动方式如下图所示。

输入格式

仅有一行，包含一个字母和数字间隔的字符串，先字母再数字，字母仅可能是大写的 A

到 H，数字只可能是 1 到 8，描述国王和骑士的坐标位置，第一个是国王的坐标，后面都是

骑士的坐标，显然字母是列号，数字是行号。

输出格式

仅有一个数，表示题目要求的最少步数。

样例输入

D4A3A8H1H8

样例输出

数据范围

字符串的长度不会超过 128。

  1 #include<iostream>
  2 #include<cmath>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<cstdlib>
  6 #include<algorithm>
  7 #define MAXN 101010
  8 using namespace std;
  9 //一个横坐标一个纵坐标，顺序赋值，骑士走的八个格 
 10 int dir[8][2] = {{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}};
 11 int distK[2][65][65]; //0:表骑士;1:表国王
 12 int pos[65][2];
 13 int num=0;
 14  
 15 bool inRange(int row, int col)
 16 {
 17     return row >= 0 && row < 8 && col >= 0 && col < 8;
 18 }
 19 //初始化格子之间的最短距离, 同时将骑士可走的格子之间的距离设置为1
 20 void init()
 21 {
 22     int i,j,k,nr,nc,p1,p2;
 23     for(i=0;i<64;i++)
 24         for(j=0;j<64;j++)
 25         {
 26             if(i==j)
 27                 distK[0][i][j]=distK[1][i][j]=0;  //当前位置到当前位置 
 28             else
 29                 distK[0][i][j]=distK[1][i][j]=MAXN;  //初始化 
 30         }
 31     for(i=0;i<8;i++)
 32         for(j=0;j<8;j++)
 33             for(k=0;k<8;k++)
 34             {
 35                 nr=i+dir[k][0];  //横坐标 
 36                 nc=j+dir[k][1];  //纵坐标 
 37                 if(inRange(nr, nc))  //未出界 
 38                 {
 39                     p1=i*8+j;
 40                     p2=nr*8+nc;
 41                     distK[0][p1][p2]=1;  //骑士走一步 
 42                 }
 43             }
 44 }
 45 //计算任意两个格子之间的最短距离
 46 void floyd()
 47 {
 48     int i,j,k,dij,dik,dkj,last=0,cur;
 49     for(k=0;k<64;k++)
 50         for(i=0;i<64;i++)
 51             for(j=0;j<64;j++)
 52                 distK[0][i][j]=min(distK[0][i][k]+distK[0][k][j],distK[0][i][j]);
 53 }
 54 void getRes()
 55 {
 56     int res=MAXN;
 57     int i,j,k,distS,d1,d2,row,col;
 58     for(i=0;i<64;i++)  //枚举最终的交汇点
 59     {
 60         distS=0;
 61         for(j=1;j<num;j++)//计算所有骑士到这个点的距离总和
 62             distS+=distK[0][i][pos[j][0]*8+pos[j][1]];  //这里才是计算步数,个数迭加       
 63         for(j=0;j<64;j++)//枚举所有国王可能和骑士的相遇点
 64         {
 65             row=j/8;
 66             col=j-row*8;
 67             d1=max(abs(pos[0][0]-row), abs(pos[0][1]-col));//d1是国王到j位置的距离
 68             //枚举所有骑士,寻找这个骑士到j的距离再加上从j到i的距离然后减去骑士到i距离的最小值
 69             d2=MAXN;
 70             for(k=1;k<num;k++)  //国王已经算过了，所以少一个 
 71             {
 72                 int curd=0;
 73                 //p为骑士的位置
 74                 int p=pos[k][0]*8+pos[k][1];
 75                 curd=distK[0][p][j]+distK[0][j][i]-distK[0][p][i]; //前面已经加了所有骑士的距离，这里要减掉带着国王的骑士的距离，重新算 
 76                 if(curd<d2) d2=curd;  //找所有骑士中最适合带国王的 
 77             }
 78             //distS + d1 + d2是当前总的距离
 79             res=min(res,distS+d1+d2);
 80         }
 81     }
 82     printf("%d",res);
 83 }
 84 int main()
 85 {
 86     int i;
 87     char s[150];
 88     scanf("%s",&s);
 89     int l=strlen(s);
 90     num=l/2;   //input.length()是求字符串input的长度 
 91     for(i=0;i<num;i++)
 92     {
 93         pos[i][1]=s[i*2]-'A';   
 94         pos[i][0]=s[i*2+1]-'1';
 95     }
 96     init();
 97     floyd();
 98     getRes();
 99 
100 }

POJ 1178