Responsive image

问题 1641 --[USACO 3.3.3]亚瑟王的宫殿

1641: [USACO 3.3.3]亚瑟王的宫殿

时间限制: 1 Sec  内存限制: 64 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

写一个程序去计算他们集中在一起的最小步数，而且玩家必须自己找出这个集中点。当然，这些棋子可以在棋盘的任何地方集合。

输入描述

第一行： 两个用空格隔开的整数：R,C 分别为棋盘行和列的长。不超过26列，40行。 第二行..结尾： 输入文件包含了一些有空格隔开的字母/数字对，一行有一个或以上。第一对为国王的位置，接下来是骑士的位置。可能没有骑士，也可能整个棋盘都是骑士。行从1开始，列从大写字母A开始。

输出描述

单独一行表示棋子集中在一个方格的最小步数。

样例输入

8 8
D 4
A 3 A 8
H 1 H 8
国王位置在D4。一共有四个骑士，位置分别是A3,A8,H1和H8。

样例输出

10


他们集中在B5。
骑士1: A3 - B5 (1步) 
骑士2: A8 - C7 - B5 (2步) 
骑士3: H1 - G3 - F5 - D4 (picking up king) - B5 (4步) 
骑士4: H8 - F7 - D6 - B5 (3步) 
1 + 2 + 4 + 3 = 10步.

来源

USACO Train 

[提交][状态]
ACM算法攻关部