using System; using System.Collections.Generic; using System.IO; using System.Linq; class Solution { enum Cell { Start, End, Empty, UL, UR, R, LR, LL, L } struct Cord { public int X; public int Y; public Cord(int x, int y) { X = x; Y = y; } } static bool ifa(Cell[,] board, int x, int y, int n, Cell cell, Queue q) { if ((x >= 0) && (y >= 0) && (x < n) && (y < n) && (board[x, y] == Cell.Empty)) { board[x, y] = cell; q.Enqueue(new Cord(x,y)); return true; } return false; } // wiersz kolumna static void printShortestPath(int n, int i_start, int j_start, int i_end, int j_end) { Cell[,] board= new Cell[n,n]; for(int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { board[i,j] = Cell.Empty; } } board[i_start, j_start] = Cell.Start; //board[i_end, j_end] = Cell.End; Queue q = new Queue(); q.Enqueue(new Cord(i_start, j_start)); while (q.Any()) { var c = q.Dequeue(); if ((c.X == i_end) && (c.Y == j_end)) { int x = i_end; int y = j_end; List solution = new List(); while((x != i_start) || (y != j_start)) { string s = board[x, y].ToString(); solution.Add(s); switch (board[x,y]) { case Cell.UL: x += 2; y += 1; break; case Cell.UR: x += 2; y -= 1; break; case Cell.R: y -= 2; break; case Cell.LR: x -= 2; y -= 1; break; case Cell.LL: x -= 2; y += 1; break; case Cell.L: y += 2; break; } } Console.WriteLine(solution.Count); for(int k= solution.Count -1; k >= 0; --k) { Console.Write(solution[k] + " "); } return; } ifa(board, c.X - 2, c.Y - 1, n, Cell.UL, q); ifa(board, c.X - 2, c.Y + 1, n, Cell.UR, q); ifa(board, c.X , c.Y + 2, n, Cell.R, q); ifa(board, c.X + 2, c.Y + 1, n, Cell.LR, q); ifa(board, c.X + 2, c.Y - 1, n, Cell.LL, q); ifa(board, c.X , c.Y - 2, n, Cell.L, q); } Console.WriteLine("Impossible"); } 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); } }