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) { // Print the distance along with the sequence of moves. // Print the distance along with the sequence of moves. //initialize start node. Node startNode = new Node(i_start, j_start, n, "start", null); startNode.PreNode = null; //root node. Node goalNode = new Node(i_end, j_end, n, "goal", null); //find goal by order of Priority: UL, UR, R, LR, LL, L //build a queue (BFS), that generate possible node (state) until meet the goal. Queue queue = new Queue(); Node pNode = startNode; BuildQueueState(pNode, ref queue, goalNode); bool bStatus = false; while (queue.Count > 0 && bStatus == false) { //process queue. //get first item in queue. Node pTmp = queue.Dequeue(); bStatus = BuildQueueState(pTmp, ref queue, goalNode); if (queue.Count >= n * n) break; //Impossible } if (bStatus == false) //can't find goal Console.WriteLine("Impossible"); } //genarate all possible state until meet goal private static bool BuildQueueState(Node pNode, ref Queue queue, Node goalNode) { //find goal by order of Priority: UL, UR, R, LR, LL, L if (pNode.UL != null && pNode.UL.Equals(goalNode)) { //find goal. PrintPath(pNode.UL); return true; //find goal } if (pNode.UR != null && pNode.UR.Equals(goalNode)) { //find goal. PrintPath(pNode.UR); return true; //find goal } if (pNode.PR != null && pNode.PR.Equals(goalNode)) { //find goal. PrintPath(pNode.PR); return true; //find goal } if (pNode.LR != null && pNode.LR.Equals(goalNode)) { //find goal. PrintPath(pNode.LR); return true; //find goal } if (pNode.LL != null && pNode.LL.Equals(goalNode)) { //find goal. PrintPath(pNode.LL); return true; //find goal } if (pNode.PL != null && pNode.PL.Equals(goalNode)) { //find goal. PrintPath(pNode.PL); return true; //find goal } //add all to queue if not finding goal. if (pNode.UL != null) queue.Enqueue(pNode.UL); if (pNode.UR != null) queue.Enqueue(pNode.UR); if (pNode.PR != null) queue.Enqueue(pNode.PR); if (pNode.LR != null) queue.Enqueue(pNode.LR); if (pNode.LL != null) queue.Enqueue(pNode.LL); if (pNode.PL != null) queue.Enqueue(pNode.PL); return false; //continue to find } //print path to current Node private static void PrintPath(Node node) { List lstString = new List(); Node pTmp = node; while (pTmp != null) { lstString.Add(pTmp.Name); pTmp = pTmp.PreNode; } //print path string path = string.Empty; for (int i = lstString.Count - 2; i >= 0; i --) { path = path + lstString[i] + " "; } //remove trailing if any. path = path.TrimEnd(' '); //write output Console.WriteLine(lstString.Count - 1); Console.WriteLine(path); } 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); } } public class Node { Node _pre = null; internal Node PreNode { get { return _pre; } set { _pre = value; } } Node _uL = null; internal Node UL { get { //king move upper left //row = row - 2, col = col - 1 int newRow = _row - 2; int newCol = _col - 1; //check for validation if (newRow < 0 || newCol < 0) return null; return new Node(newRow, newCol, _gridSize, "UL", this); } set { _uL = value; } } Node _uR = null; internal Node UR { get { //king move upper right //row = row - 2, col = col + 1 int newRow = _row - 2; int newCol = _col + 1; //check for validation if (newRow < 0 || newCol >= _gridSize) return null; return new Node(newRow, newCol, _gridSize, "UR", this); } set { _uR = value; } } Node _lL = null; internal Node LL { get { //king move low left //row = row + 2, col = col - 1 int newRow = _row + 2; int newCol = _col - 1; //check for validation if (newRow >= _gridSize || newCol < 0) return null; return new Node(newRow, newCol, _gridSize, "LL", this); } set { _lL = value; } } Node _lR = null; internal Node LR { get { //king move low right //row = row + 2, col = col + 1 int newRow = _row + 2; int newCol = _col + 1; //check for validation if (newRow < 0 || newCol >= _gridSize) return null; return new Node(newRow, newCol, _gridSize, "LR", this); } set { _lR = value; } } Node _pL = null; internal Node PL { get { //king move left //row = row, col = col - 2 int newRow = _row; int newCol = _col - 2; //check for validation if (newRow < 0 || newCol < 0) return null; return new Node(newRow, newCol, _gridSize,"L", this); } set { _pL = value; } } Node _pR = null; internal Node PR { get { //king move right //row = row, col = col + 2 int newRow = _row; int newCol = _col + 2; //check for validation if (newRow < 0 || newCol >= _gridSize) return null; return new Node(newRow, newCol, _gridSize,"R", this); } set { _pR = value; } } int _row = -1; public int Row { get { return _row; } set { _row = value; } } int _col = -1; public int Col { get { return _col; } set { _col = value; } } int _gridSize = 0; string _name = string.Empty; public string Name { get { return _name; } set { _name = value; } } public Node(int row, int col, int gridSize, string name, Node preNode) { _row = row; _col = col; _gridSize = gridSize; _name = name; _pre = preNode; } public bool Equals(Node obj) { return (this.Row == obj.Row && this.Col == obj.Col); } ///check to see whether the current node is making a loop or not public bool IsMakingLoop() { Node pTemp = _pre; while (pTemp != null) { if (pTemp.Equals(this)) return true; pTemp = pTemp.PreNode; } return false; } }