<分区>
我正在做一个问题 CCHESS,这里是问题的链接(http://www.spoj.pl/problems/CCHESS/)。
题目如下:
在罗马这个国家,国际象棋是一种皇家游戏。对于每一步,玩家都必须给 Emperor Jurg 一些钱。 LGM 或 Little Green Men 是非常好的国际象棋棋手。但由于国际象棋是一种昂贵的游戏,这就是为什么它是皇家的,他们要求你帮助他们找到将他们的马从一个位置移动到另一个位置所必须支付的最低金额。可以使用任意数量的步骤到达目的地。
约束:
国际象棋的尺寸为 8X8,左下角单元格的索引为 (0, 0)。
马只能以标准方式移动,即 2 行和 1 列或 1 行和 2 列。
如果 Knight 在一步中从 (a, b) 移动到 (c, d),则 LGM 必须向 Emperor Jurg 支付 a*c + b*d 美元。
0 ≤ a, b, c, d ≤ 7
输入
有 100-150 个测试用例。每个测试用例由四个空格分隔的整数组成。前两个数字 a、b 是 Knight 的起始位置,接下来的两个 c、d 是 Knight 的目的地。读到文件结尾。 输出
对于每个测试用例,在单独的行中打印出他们必须支付的最低金额。如果无法到达目的地,则打印 -1。
例子
输入:
2 5 5 2
4 7 3 2
1 2 3 4
输出:
42 78 18
测试用例 #1 的解释: 2 5 5 2
用于移动骑士 (2, 5) 到 (5, 2)
in minimum cost, one of the path is
(2, 5) -> (3, 3) ->(5, 2)
支付的金额:
(2, 5) = 0
(2, 5) -> (3, 3) = 0 + (2*3 + 5*3) = 21
(3, 3) -> (5, 2) = 21 + (3*5 + 3*2) = 42
到无限远...
我已经使用蛮力解决了这个问题,即递归检查所有可能的路径,但我认为我在某个地方找不到直接方法,因为许多提交都是 0.00,而我的递归方法在 0.3s 中被接受。 任何帮助将不胜感激。