using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { public enum MoveType { UL, UR, R, LR, LL, L}; static MoveType GetBestMoveType(int i_start, int j_start, int i_end, int j_end, int n) { MoveType mt = MoveType.UL; if (i_start > i_end) { if (j_start >= j_end) { mt = MoveType.UL; } else if (j_start < j_end) { if ((j_end != j_start) && (Math.Abs((i_end - i_start) / (j_end - j_start)) > 2) && (j_start > 1)) mt = MoveType.UL; else mt = MoveType.UR; } } else if (i_start < i_end) // lower families of moves { if (j_start > j_end) { if (((j_end != j_start) && Math.Abs((float)(i_end - i_start) / (float)(j_end - j_start)) > 2) && (j_start < (n - 2))) mt = MoveType.LR; else mt = MoveType.LL; } else if (j_start <= j_end) { if (((i_end != i_start) && Math.Abs((float)(j_end - j_start)/ (float)(i_end - i_start)) > 0.5) && (j_start < (n - 2))) mt = MoveType.R; else mt = MoveType.LR; } } else // i_start == i_end { if (j_start > j_end) { mt = MoveType.L; } else if (j_start <= j_end) { mt = MoveType.R; } } return mt; } static bool WillMove(List moves, int n, int i_start, int j_start, int i_end, int j_end) { bool rv = false; MoveType mt = GetBestMoveType(i_start, j_start, i_end, j_end, n); int i_new = 0, j_new = 0; while (moves.Count < (n * n)) { if (Move(mt, n, i_start, j_start, out i_new, out j_new)) { moves.Add(mt); if ((i_new != i_end) || (j_new != j_end)) { i_start = i_new; j_start = j_new; mt = GetBestMoveType(i_start, j_start, i_end, j_end, n); } else { break; // hit exit condition: have hit the end point } } else { break; // impossible! } } rv = (i_new == i_end) && (j_new == j_end); return rv; } static 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. // see https://www.hackerrank.com/contests/world-codesprint-12/challenges/red-knights-shortest-path // preference order UL, UR, R, LR, LL, L List moves = new List(); bool response = WillMove(moves, n, i_start, j_start, i_end, j_end); if (response) { System.Console.Out.WriteLine(moves.Count); System.Console.Out.WriteLine(String.Join(" ", moves.ToArray())); } else { System.Console.Out.WriteLine("Impossible"); } } static bool Move(MoveType mt, int n, int i_start, int j_start, out int i_new, out int j_new) { bool rv = false; i_new = i_start; j_new = j_start; switch (mt) { case MoveType.L: if ((j_new - 2) >= 0) { j_new -= 2; rv = true; } break; case MoveType.LL: if (((i_new + 2) < n) && ((j_new - 1) >= 0)) { i_new += 2; j_new--; rv = true; } break; case MoveType.LR: if (((i_new + 2) < n) && ((j_new + 1) < n)) { i_new += 2; j_new++; rv = true; } break; case MoveType.R: if ((j_new + 2) < n) { j_new += 2; rv = true; } break; case MoveType.UL: if (((i_new - 2) >= 0) && ((j_new - 1) >= 0)) { i_new -= 2; j_new--; rv = true; } break; case MoveType.UR: if (((i_new - 2) >= 0) && ((j_new + 1) < n)) { i_new -= 2; j_new++; rv = true; } break; } return rv; } static void Main(String[] args) { int n = Convert.ToInt32(Console.ReadLine()); string[] tokens_i_start = Console.ReadLine().Split(' '); int i_start = Convert.ToInt32(tokens_i_start[0]); int j_start = Convert.ToInt32(tokens_i_start[1]); int i_end = Convert.ToInt32(tokens_i_start[2]); int j_end = Convert.ToInt32(tokens_i_start[3]); printShortestPath(n, i_start, j_start, i_end, j_end); } }