The correct, optimal and working solution for programming question CCHESS on spoj

#include <iostream> #include <list> #include <climits> #include <cstdio> using namespace std; struct node { int node_number; int cost; }; void create_graph ( int r , int c , list<struct node *> * list_ ) { int a = r * 8 + c; int n , m; n = r + 2; m = c + 1; if ( n >= 0 && n <= 7 && m >= 0 && m <= 7 ) { struct node * nd = new struct node; nd->node_number = n*8 + m; nd->cost = r*n + c*m; list_[a].push_back(nd); } n = r + 2; m = c - 1; if ( n >= 0 && n <= 7 && m >= 0 && m <= 7 ) { struct node * nd = new struct node; nd->node_number = n*8 + m; nd->cost = r*n + c*m; list_[a].push_back(nd); } n = r - 2; m = c + 1; if ( n >= 0 && n <= 7 && m >= 0 && m <= 7 ) { struct node * nd = new struct node; nd->node_number = n*8 + m; nd->cost = r*n + c*m; list_[a].push_back(nd); } n = r - 2; m = c - 1; if ( n >= 0 && n <= 7 && m >= 0 && m <= 7 ) { struct node * nd = new struct node; nd->node_number = n*8 + m; nd->cost = r*n + c*m; list_[a].push_back(nd); } n = r + 1; m = c + 2; if ( n >= 0 && n <= 7 && m >= 0 && m <= 7 ) { struct node * nd = new struct node; nd->node_number = n*8 + m; nd->cost = r*n + c*m; list_[a].push_back(nd); } n = r + 1; m = c - 2; if ( n >= 0 && n <= 7 && m >= 0 && m <= 7 ) { struct node * nd = new struct node; nd->node_number = n*8 + m; nd->cost = r*n + c*m; list_[a].push_back(nd); } n = r - 1; m = c + 2; if ( n >= 0 && n <= 7 && m >= 0 && m <= 7 ) { struct node * nd = new struct node; nd->node_number = n*8 + m; nd->cost = r*n + c*m; list_[a].push_back(nd); } n = r - 1; m = c - 2; if ( n >= 0 && n <= 7 && m >= 0 && m <= 7 ) { struct node * nd = new struct node; nd->node_number = n*8 + m; nd->cost = r*n + c*m; list_[a].push_back(nd); } } int dijkstra ( int s , int t , list<struct node *> *list_ ) { int dist[64]; int visited[64]; for ( int i = 0 ; i < 64 ; i++ ) { dist[i] = INT_MAX; visited[i] = 0; } dist[s] = 0; while ( s != -1 ) { visited[s] = 1; for ( list<struct node *>::iterator itr = list_[s].begin() ; itr != list_[s].end() ; itr++ ) { struct node * v = (*itr); if ( visited[v->node_number] == 1 ) continue; if ( dist[v->node_number] > dist[s] + v->cost ) { dist[v->node_number] = dist[s] + v->cost; } } s = -1; int min_distance = INT_MAX; for ( int i = 0 ; i < 64 ; i++ ) { if ( visited[i] == 0 && dist[i] < min_distance ) { s = i; min_distance = dist[i]; } } } return dist[t]; } int main ( int argc , char * argv[] ) { list<struct node *> * list_ = new list<struct node *>[64]; for ( int i = 0 ; i < 8 ; i ++ ) { for ( int j = 0 ; j < 8 ; j++ ) { create_graph( i , j , list_ ); } } /*for ( int i = 0 ; i < 64 ; i++ ) { cout << "Node " << i << " : "; for ( list<struct node *>::iterator itr = list_[i].begin() ; itr != list_[i].end() ; itr++ ) { cout << " " << (*itr)->node_number; } cout << endl; }*/ int r1,c1,r2,c2; while ( scanf("%d%d%d%d" , &r1 , &c1 , &r2 , &c2 ) != EOF ) { cout << dijkstra ( r1 * 8 + c1 , r2 * 8 + c2 , list_ ) << endl; } return 0; }