#include #include void swap(int *xp, int *yp) { int temp = *xp; *xp = *yp; *yp = temp; } // A function to implement bubble sort void bubbleSort(int arr[], int n) { int i, j; for (i = 0; i < n-1; i++) // Last i elements are already in place for (j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(&arr[j], &arr[j+1]); } /* Function to print an array */ void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { //int arr[201][201]; int arr[10000]; int i,j; int count=0; //int steps=0; int flag1=0,flag2=0; if(i_start==i_end && j_start==j_end) { printf("%d",0); } else { i=i_start; j=j_start; if(i_start>i_end) { while(1) { if(i<0 || i>=n || j<0 || j>=n) { printf("Impossible\n"); break; } if((j_end-j)>0 && i!=i_end) { arr[count]=2; count++; i=i-2; j=j+1; } else if((j_end-j)<0 && i!=i_end) { arr[count]=1; count++; i=i-2; j=j-1; } else if((j_end-j)==0 && i!=i_end) { if(j==0) { arr[count]=2; count++; i=i-2; j=j+1; } else { arr[count]=1; count++; i=i-2; j=j-1; } } else { if((j_end-j)>0) { arr[count]=3; count++; if(flag2==1) { printf("Impossible\n"); break; } flag1=1; j=j+2; } else if((j_end-j)<0) { arr[count]=6; count++; if(flag1==1) { printf("Impossible\n"); break; } flag2=1; j=j-2; } else { printf("%d\n",count); for(i=0;i=n || j<0 || j>=n) { printf("Impossible\n"); break; } if((j_end-j)>0 && i!=i_end) { arr[count]=5; count++; i=i-2; j=j+1; } else if((j_end-j)<0 && i!=i_end) { arr[count]=4; count++; i=i-2; j=j-1; } else if((j_end-j)==0 && i!=i_end) { if(j==0) { arr[count]=5; count++; i=i-2; j=j+1; } else { arr[count]=4; count++; i=i-2; j=j-1; } } else { if((j_end-j)>0) { arr[count]=6; count++; if(flag2==1) { printf("Impossible\n"); break; } flag1=1; j=j+2; } else if((j_end-j)<0) { arr[count]=3; count++; if(flag1==1) { printf("Impossible\n"); break; } flag2=1; j=j-2; } else { printf("%d\n",count); bubbleSort(arr,count); for(i=0;i=n || j<0 || j>=n ) { printf("Impossible\n"); break; } if((j_end-j)>0) { arr[count]=3; count++; if(flag2==1) { printf("Impossible\n"); break; } flag1=1; j=j+2; } else if((j_end-j)<0) { arr[count]=6; count++; if(flag1==1) { printf("Impossible\n"); break; } flag2=1; j=j-2; } else { printf("%d\n",count); for(i=0;i