SPOJ CCHESS (昂贵的国际象棋)

Question

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

问题如下：

在罗马，国际象棋是一项皇家游戏。每走一步，玩家都要给尤尔格皇帝一些钱。LGM或小绿人，是非常好的棋手。但由于国际象棋是一种昂贵的游戏，这就是为什么它是皇家的，他们要求你帮助他们找到他们必须支付的最低金额，以将他们的骑士从一个位置移动到另一个位置。可以使用任意数量的步骤来到达目的地。

约束条件：

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

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

如果骑士在一个步骤中从(a，b)移动到(c，d)，那么LGM必须向尤尔格皇帝支付a*c + b*d美元。

0 ≤ a, b, c, d ≤ 7

输入

有100-150个测试用例。每个测试用例由四个空格分隔的integers.The组成，前两个数字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.3秒内就被接受了。任何帮助都将不胜感激。

Answer 1

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.

Answer 2

尝试A*算法，启发式=曼哈顿距离/3。