0

我正在做一个问题 CCHESS，这里是问题的链接（http://www.spoj.pl/problems/CCHESS/）。

问题如下：

在罗马这个国家，国际象棋是一种皇家游戏。对于每一个动作，玩家都必须给皇帝 Jurg 一些钱。LGM 或小绿人是非常优秀的国际象棋手。但是由于国际象棋是一种昂贵的游戏，这就是它是皇家的原因，他们要求你帮助他们找到将他们的骑士从一个位置移动到另一个位置所必须支付的最低费用。可以使用任意数量的步骤到达目的地。

约束：

国际象棋的尺寸为 8X8，左下单元格的索引为 (0, 0)。

骑士只能以标准方式移动，即 2 行 1 列或 1 行 2 列。

如果骑士一步从 (a, b) 移动到 (c, d)，那么 LGM 必须向皇帝 Jurg 支付 a*c + b*d 美元。

0 ≤ a, b, c, d ≤ 7

输入

有 100-150 个测试用例。每个测试用例由四个空格分隔的整数组成。前两个数字 a、b 是骑士的起始位置，接下来的两个数字 c、d 是骑士的目的地。读到文件结尾。输出

对于每个测试用例，在单独的行中打印他们必须支付的最低金额。如果无法到达目的地，则打印-1。

例子

输入：

2 5 5 2
4 7 3 2
1 2 3 4

输出：

42 78 18

测试用例 #1 的说明：2 5 5 2

用于将 Knight 从 (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 被接受。任何帮助，将不胜感激。

4

2 回答 2

2 
Construct a graph G=(V,E) where 
V is the set of coordinates in the grid {v=(x,y)} 
E is the set of edges between vertices
Assign weights on the edges where weight is (v1.x * v2.x + v1.y*v2.y) 
Use Dijkstra's algorithm to find the shortest path (1 source - 1 destination)
source = (a,b) and destination = (c,d)
If there is no path report -1.

The number of vertices are limited to (8*8) = 64
The number of edges are limited to 64 * (8) = 512 
as the knight can move to at most 8 other coordinates from one place.
于 2012-09-14T08:31:55.817 回答
0

尝试 A* 算法，使用 heuristic = manhattan_distance/3 。

于 2012-09-14T08:34:05.537 回答