SPOJ CCHESS（昂贵的国际象棋） [英] SPOJ CCHESS ( Costly Chess )

问题描述

我在做CCHESS问题，这是链接（ http://www.spoj.pl / problems / CCHESS / ）解决问题。

I am doing a problem CCHESS, here is the link ( http://www.spoj.pl/problems/CCHESS/ ) to the problem.

问题如下：

在罗马国家，国际象棋是一种皇家游戏。为了做出举动，球员们不得不给吉尔皇帝一些钱。 LGM或Little Green Men是非常好的国际象棋棋手。但是由于国际象棋是一种昂贵的游戏，这就是为什么它是皇家的，他们要求您帮助他们找到将骑士从一个位置调到另一个位置所必须支付的最低费用。

In the country of Rome, Chess is a royal game. For evey move the players had to give some bucks to the Emperor Jurg. The LGMs or Little Green Men, are very good player of chess. But as the chess is a expensive game, thats why it is royal, they asked you to help them find the minimum bucks which they had to pay for moving their Knight from one position to another. Any number of steps can be used to reach the destination.

约束：

国际象棋的尺寸为8X8，以及左下方单元格的索引（0，0）。

The chess has a dimension of 8X8, and the index of left bottom cell (0, 0).

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

Knight move only in a standard way, i.e. 2 row and 1 col or 1 row and 2 col.

如果骑士从（a，b）移至（c，d），那么LGM必须向皇帝支付a * c + b * d美元

If in a step Knight move from (a, b) to (c, d), then LGM had to pay a*c + b*d bucks to Emperor Jurg.

0 ≤ a, b, c, d ≤ 7

输入

有100-150个测试用例。每个测试用例都由四个空格分隔的整数组成。前两个数字a，b是Knight的起始位置，后两个数字c，d是Knight的目的地。读取到文件末尾。
输出

There are 100-150 test cases. Each test case is composed of four space separeated integers.The first two numbers, a, b, are the starting position of the Knight and the next two, c, d, are the destination of the Knight. Read upto End Of File. Output

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

For each test case, print the minimum amount of bucks they had to pay in separate line. If its impossible to reach the destination then print -1.

示例

输入：

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

输出：

42
78
18

42 78 18

测试用例1的解释：
2 5 5 2

Explanation for test case #1: 2 5 5 2

从
移动骑士（ 2，5）到（5，2）

For moving Knight from (2, 5) to (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.3秒内被接受，大量的提交都是0.00。
任何帮助将不胜感激。

I have done this problem using brute force, i.e. checking recursively all the possible paths but i think i am missing somewhere to find a direct approach, because numerous submissions are of 0.00 where as my recursive approach got accepted in 0.3s . Any help would be appreciated.

推荐答案

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.

这篇关于SPOJ CCHESS（昂贵的国际象棋）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！