#include #include #include #include #include #include #include void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { // Print the distance along with the sequence of moves. int u,v; int i0,i1,j0,j1,num; int mv[256]; u = i_end > i_start ? i_end - i_start : i_start - i_end; if((u%2)!=0){ printf("Impossible\n"); return; } v = j_end > j_start ? j_end - j_start : j_start - j_end; v += u/2; if((v%2)!=0){ printf("Impossible\n"); return; } u/=2; i0 = i_start; j0 = j_start; i1 = i_end; j1 = j_end; if(i0==i1){ if(j1 > j0){ num = (j1-j0)/2; printf("%d\n",num); for(u=0;u=j1){ mv[num] = 1; i0-=2; j0-=1; u--; } else { mv[num] = 2; i0-=2; j0+=1; u--; } } else if((i1==i0)&&(j1>j0)){ mv[num] = 3; j0+=2; } else if(i1>i0){ if(j1>(j0+u)){ mv[num] = 3; j0+=2; } else if(j0==n-1){ mv[num] = 5; i0+=2; j0-=1; u--; } else if(((j0+1)-(u-1))<=j1){ mv[num] = 4; i0+=2; j0+=1; u--; } else { mv[num] = 5; i0+=2; j0-=1; u--; } } else { mv[num] = 6; j0-=2; } // printf("%d %d -> %d %d\n",num,mv[num],i0,j0); num++; } printf("%d\n",num); for(u=0;u