6853 - 3.3.3 Camelot 亚瑟王的宫殿

15658512416335.png

输入

第一行: 两个用空格隔开的整数:R,C 分别为棋盘行和列的长.不超过 26 列,40 行.

第二行..结尾: 输入文件包含了一些有空格隔开的字母/数字对,一行有一个或以上.第一对为国王的位置,接下来是骑士的位置.可能没有骑士,也可能整个棋盘都是骑士.行从 1 开始,列从大写字母A 开始.

输出

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

样例

输入

8 8

A  4

A 3 A 8

H 1 H 8

国王位置在 D4.一共有四个骑士,位置分别是 A3,A8,H1 和 H8.

输出

10

提示

HINT

他们集中在 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

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题