## CCHESS - COSTLY CHESS

no tags

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.

Constraints:

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

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

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

### Input

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

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.

### Example

`Input:2 5 5 24 7 3 21 2 3 4Output:427818Explanation for test case #1:2 5 5 2For moving Knight from (2, 5) to (5, 2) in minimum cost,  one of the path is (2, 5) -> (3, 3) ->(5, 2)Bucks paid:(2, 5)              =  0(2, 5) -> (3, 3) =  0 + (2*3 + 5*3) = 21(3, 3) -> (5, 2) = 21 + (3*5 + 3*2) = 42     To infinity and beyond...`

hide comments
 < Previous 1 2 3 Next > tito_916: 2021-05-06 06:42:20 can anyone tell how to check eof condition.i am using cin.eof() in loop condition but it is giving wrong answer.but my code is fine and passing all the edge cases also satyam_656: 2021-04-01 12:12:11 Dijkstra on 2D grid karthik_2: 2021-01-24 05:52:57 AC in one go with djs and priority queue. explodingfrz: 2019-06-15 11:20:49 Easy problem with BFS or Dijkstra , just ensure not to use !cin.eof as the loop condition... caused me to get a WA for no reason... put the cin statement as the loop condition and got easy AC marethyu1: 2019-05-25 01:07:48 super easy problem! suraj_13: 2019-01-20 09:55:15 @ahmedgu no one is going to fall in the trap sagar_june97p: 2019-01-18 14:29:44 Do not use while(!cin.eof()), cost me 2 WA nidhi_061: 2018-06-22 07:37:42 Last edit: 2018-09-15 13:03:25 v_pp_27: 2018-02-15 06:10:01 solve NAKANJ first then just use priority_queue instead of queue ahmedgu: 2017-11-15 13:52:39 simple dp + dijkstra + backtracking + segment tree + binary search and little bit of geometry. Happy Coding :D

 Added by: abhiranjan Date: 2011-02-18 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All Resource: IIITM Local Contest