CCHESS  COSTLY CHESS
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 100150 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 2
4 7 3 2
1 2 3 4
Output:
42
78
18
Explanation for test case #1:
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)
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
nidhi_061:
20180622 07:37:42
Last edit: 20180915 13:03:25 

v_pp_27:
20180215 06:10:01
solve NAKANJ first


ahmedgu:
20171115 13:52:39
simple dp + dijkstra + backtracking + segment tree + binary search and little bit of geometry. Happy Coding :D 

supriyanta:
20171010 18:48:57
AC in one go! simple dijkstra :) 

prateek:
20170329 14:39:27
Any other solution rather than using priority_queue and bfs .Can we use backtracking? 

pvsmpraveen:
20170329 12:45:50
priority_queue :D 

vanvinhbk94:
20170222 08:04:13
AC in one go 

vengatesh15:
20170123 13:34:06
simple bfs AC in 1 go Last edit: 20170123 13:34:32 

:.Mohib.::
20151022 11:48:22
Very Nice Question....!! 

gandalf_:
20150901 12:07:18
This is like NAKANJ except for the starting cell.

Added by:  abhiranjan 
Date:  20110218 
Time limit:  0.151s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  IIITM Local Contest 