#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 i,j,count=0,hor,vet,result[n]; if (abs(i_start-i_end)%2==1) { printf("Impossible\n"); return; } else { if (abs(i_start-i_end)%4==0 && abs(j_end-j_start)%2==1) { printf("Impossible\n"); return; } else if (abs(i_start-i_end)%4==2 && abs(j_end-j_start)%2==0) { printf("Impossible\n"); return; } else { if (i_start>=i_end) { vet=i_start-i_end; if (j_start>=j_end) { hor=j_start-j_end; vet/=2; if (vet>=hor) //region1 { count=vet; i=0; vet-=hor; for(;hor!=0;hor--,i++) result[i]=0; for(;vet!=0;vet-=2) { result[i]=0; result[i+1]=1; i+=2; } } else //region2 { hor-=vet; count=vet+(hor/2); i=0; for(;vet!=0;vet--,i++) result[i]=0; for(;hor!=0;hor-=2,i++) result[i]=5; } } else { hor=j_end-j_start; vet/=2; if (vet>=hor) //region3 { count=vet; i=0; vet-=hor; for(;hor!=0;hor--,i++) result[i]=1; for(;vet!=0;vet-=2) { result[i]=0; result[i+1]=1; i+=2; } } else //region4 { hor-=vet; count=vet+(hor/2); i=0; for(;vet!=0;vet--,i++) result[i]=1; for(;hor!=0;hor-=2,i++) result[i]=2; } } } else if (i_start=j_end) { hor=j_start-j_end; vet/=2; if (vet>=hor) //region1 { count=vet; i=0; vet-=hor; for(;hor!=0;hor--,i++) result[i]=4; for(;vet!=0;vet-=2) { result[i]=3; result[i+1]=4; i+=2; } } else //region2 { hor-=vet; count=vet+(hor/2); i=0; for(;vet!=0;vet--,i++) result[i]=4; for(;hor!=0;hor-=2,i++) result[i]=5; } } else { hor=j_end-j_start; vet/=2; if (vet>=hor) //region3 { count=vet; i=0; vet-=hor; for(;hor!=0;hor--,i++) result[i]=3; for(;vet!=0;vet-=2) { result[i]=3; result[i+1]=4; i+=2; } } else //region4 { hor-=vet; count=vet+(hor/2); i=0; for(;vet!=0;vet--,i++) result[i]=3; for(;hor!=0;hor-=2,i++) result[i]=2; } } } printf("%d\n",count); for(j=0;j