using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { if((i_start-i_end)%2 != 0) { Console.WriteLine("Impossible"); return; } int iMoves = Math.Abs(i_start-i_end)/2; int jDist = Math.Abs(j_start-j_end); if((j_start-j_end-iMoves%2)%2 != 0) { Console.WriteLine("Impossible"); return; } int ULs = 0; int URs = 0; int Rs = 0; int LRs = 0; int LLs = 0; int Ls = 0; int i = i_start; int j = j_start; while(i != i_end || j != j_end) { //Console.WriteLine(i + " " + j + " " + i_end + " " + j_end); //Console.WriteLine(ULs + " " + URs + " " + Rs + " " + LRs + " " + LLs + " " + Ls); if(i > i_end) { //upwards movement UL/UR if(j > j_end) { //ULs int inc = Math.Min((i-i_end)/2, j-j_end); ULs+=inc; i-=2*inc; j-=inc; } else if (j < j_end) { //URs int inc = Math.Min((i-i_end)/2, j_end-j); URs+=inc; i-=2*inc; j+=inc; } else if(i-i_end >= 4) { //back and forth UL/UR int inc = (i-i_end)/4; ULs+=inc; URs+=inc; i-=4*inc; } else { if(j_end == 0) { // single UR URs++; j++; i-=2; } else { // single UL ULs++; j--; i-=2; } } } else if(i < i_end) { //downwards movement LR/LL if(j < j_end) { //LR int inc = Math.Min((i_end-i)/2, j_end-j); LRs+=inc; i+=2*inc; j+=inc; } else if (j > j_end) { // LL int inc = Math.Min((i_end-i)/2, j-j_end); LLs+=inc; i+=2*inc; j-=inc; } else if(i_end-i >= 4) { // back and forth LR/LL int inc = (i_end-i)/4; LLs += inc; LRs += inc; i+=4*inc; } else { if(j_end == 0) { // single LR LRs++; j++; i+=2; } else { // single LL LLs++; j--; i+=2; } } } else { if(j > j_end) { int inc = (j-j_end)/2; Ls+=inc; j-=2*inc; } else if(j < j_end) { int inc = (j_end-j)/2; Rs+=inc; j+=2*inc; } } } //Console.WriteLine(ULs + " " + URs + " " + Rs + " " + LRs + " " + LLs + " " + Ls); string res = ""; for(int k=0; k