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) { string[] adjacentSquares = new string[8]; int adjCounter = 0; int numMoves = 0; string pathDetails = ""; bool isPossible = true; int i_curr = i_start; int j_curr = j_start; // Store adjacent squares which indicate impossible outcomes for(int ii = i_end - 1; ii <= i_end + 1; ii++) { for(int jj = j_end - 1; jj <= j_end + 1; jj++) { if ((ii == i_end) && (jj == j_end)) { // This is the end square, not an adjacent one so skip continue; } adjacentSquares[adjCounter] = ii.ToString() + " " + jj.ToString(); adjCounter += 1; } } while (isPossible == true) { // First check to see if we are on the end square if ((i_curr == i_end) && (j_curr == j_end)) { break; } // See if we are on an adjacent square (if so, we are in a spot that is impossible) foreach (string s in adjacentSquares) { if (i_curr.ToString() + " " + j_curr.ToString() == s) { pathDetails = "Impossible"; numMoves = -1; isPossible = false; break; } } // If impossible move then break out if (isPossible == false) { break; } // Decide which move to make // Assign possible move locations to array (order in array reflects preference ranking) int[,] possMove = new int[6, 2]; // UL possMove[0,0] = i_curr - 2; possMove[0,1] = j_curr - 1; // UR possMove[1,0] = i_curr - 2; possMove[1,1] = j_curr + 1; // R possMove[2,0] = i_curr; possMove[2,1] = j_curr + 2; // LR possMove[3,0] = i_curr + 2; possMove[3,1] = j_curr + 1; // LL possMove[4,0] = i_curr + 2; possMove[4,1] = j_curr - 1; // L possMove[5,0] = i_curr; possMove[5,1] = j_curr - 2; // Decide which move is best int bestScore = -1; int currScore = -1; int index_bestmove = -1; for(int cntr = 0; cntr < 6; cntr++) { // Check to see if move takes us off the board, if so then skip if ((possMove[cntr, 0] < 0) || (possMove[cntr, 0] >= n) || (possMove[cntr, 1] < 0) || (possMove[cntr, 1] >= n)) { continue; } // Calculate the score for the possible move currScore = Math.Abs(possMove[cntr, 0] - i_end) + Math.Abs(possMove[cntr, 1] - j_end); // If the current score is better then the one for our current best move, then replace it if ((bestScore == -1) || (currScore < bestScore)) { bestScore = currScore; index_bestmove = cntr; } } // Record the best move string moveLabel = ""; switch(index_bestmove) { case 0: moveLabel = "UL"; break; case 1: moveLabel = "UR"; break; case 2: moveLabel = "R"; break; case 3: moveLabel = "LR"; break; case 4: moveLabel = "LL"; break; case 5: moveLabel = "L"; break; } pathDetails = pathDetails + moveLabel + ' '; // Increment move counter numMoves += 1; // Store move as current location i_curr = possMove[index_bestmove, 0]; j_curr = possMove[index_bestmove, 1]; } // Print the distance along with the sequence of moves. if (numMoves == -1) { Console.WriteLine(pathDetails); } else { Console.WriteLine(numMoves); Console.WriteLine(pathDetails); } } 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); } }