Algorithm
Problem link- https://www.spoj.com/problems/CCHESS/
CCHESS - COSTLY CHESS
In the country of Rome, Chess is a royal game. For every 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 chess is an expensive game, that's 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 column or 1 row and 2 column.
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 separated 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 up to End Of File.
Output
For each test case, print the minimum amount of bucks they had to pay in separate line. If it's 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
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) → (3, 3) = (2 * 3 + 5 * 3) = 21
- (3, 3) → (5, 2) = (3 * 5 + 3 * 2) = 21
- Total cost = 42
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <stdio.h>
#include < algorithm>
#include <iostream>
#include <iterator>
#include <numeric>
#include <sstream>
#include <fstream>
#include <cassert>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define INF 1000000000
int dx[]={2,2,-2,-2,1,-1,-1,1};
int dy[]={1,-1,-1,1,2,2,-2,-2};
int starti,startj,endi,endj;
int mincost=INF;
typedef bool (*comp)(pair<ii,int>,pair<ii,int>);
bool compare(pair<ii,int> a,pair<ii,int> b){
return a.second>b.second;
}
int vis[8][8];
int dijkstras(){
memset(vis,0,sizeof vis);
priority_queue<pair<ii,int>,vector<pair<ii,int> >,comp> pq(compare);
pq.push(pair<ii,int>(ii(starti,startj),0));
while(!pq.empty()){
pair<ii,int> top = pq.top();
pq.pop();
if(vis[top.first.first][top.first.second])
continue;
if(top.first.first==endi&&top.first.second==endj)
return top.second;
vis[top.first.first][top.first.second]=1;
for(int i=0;i<8;++i){
int cx=top.first.first+dx[i];
int cy=top.first.second+dy[i];
if(cx<0||cx>=8||cy<0||cy>=8||vis[cx][cy]){
continue;
}
int temp = (top.first.first*cx)+(top.first.second*cy)+top.second;
pq.push(pair<ii,int>(ii(cx,cy),temp));
}
}
return -1;
}
int main(){
while(scanf("%d %d %d %d", &starti,&startj,&endi,&endj)>0){
printf("%d\n",dijkstras());
}
return 0;
}Input
4 7 3 2
1 2 3 4
Output
78
18
Demonstration
SPOJ Solution-CCHESS COSTLY CHESS-Solution in C, C++, Java, Python,CCHESS COSTLY CHESS,SPOJ Solution