import scala.collection.immutable.Stream.Empty import scala.math.Ordering.Implicits._; object Solution { def printShortestPath(n: Int, i_start: Int, j_start: Int, i_end: Int, j_end: Int): Unit = { // Print the distance along with the sequence of moves. val moves:List[(Int,Int, String)] = List(); val shortest:List[(Int,Int, String)] = List(); val result = go(n, (i_end, j_end), (moves.::(i_start, j_start, ""), shortest)); result._2.slice(0, result._2.size - 1) match { case Nil => println("Impossible"); case x => { println(x.length) printThisSHit(x.length, x) } } return; } def printThisSHit(i: Int, list: List[(Int,Int, String)]){ list match { case Nil => case h::t => {printThisSHit(i-1, t) print(h._3) if(i > 0){ print(" ") } } } } def UL(cords: ((Int, Int))):((Int,Int,String)) = { return (cords._1-2, cords._2-1, "UL") } def UR(cords: ((Int, Int))):((Int, Int, String)) = { return (cords._1-2, cords._2+1, "UR") } def R(cords: ((Int, Int))):((Int, Int, String)) = { return (cords._1, cords._2+2, "R") } def LR(cords: ((Int, Int))):((Int, Int, String)) = { return (cords._1+2, cords._2+1, "LR") } def LL(cords: ((Int, Int))):((Int, Int, String)) = { return (cords._1+2, cords._2-1, "LL") } def L(cords: ((Int, Int))):((Int, Int, String)) = { return (cords._1, cords._2-2, "L") } def applyMove(cords: (Int, Int, String), size: Int, move: ((Int, Int))=>((Int, Int, String))): Either[Boolean, (Int, Int, String)] = { val destination = move(cords._1, cords._2); if(destination._1 >= size || destination._2 >= size || destination._1 < 0 || destination._2 < 0){ return Left(false); } return Right(destination) } def go(boardSize: Int, goal: ((Int, Int)), state:(List[(Int, Int, String)], List[(Int, Int, String)])): (List[(Int, Int, String)], List[(Int, Int, String)]) = { val allPossibleMoves: Array[(((Int, Int)))=>(Int, Int, String)] = Array(UL, UR, R, LR, LL, L); var counter = 0; val moves = state._1; var shortest = state._2; val head = state._1.head; var res: Option[(List[(Int, Int, String)], List[(Int, Int, String)])] = None while(counter < 6 && (moves.length < shortest.length || shortest.length ==0)){ var result = applyMove(head, boardSize, allPossibleMoves(counter)); counter += 1; result match { case Left(x) => case Right(cords) => { //println(moves); if (goal._1 == cords._1 && goal._2 == cords._2) { if (shortest.length > moves.length + 1 || shortest.length ==0) { return (moves, cords :: moves) } } if (!doesMoveExist(cords, moves)) { val (a, b) = go(boardSize, goal, (cords :: moves, shortest)); shortest = b; } }; } } return(moves, shortest) } def doesMoveExist(move: (Int, Int, String), moves: List[(Int, Int, String)]): Boolean = { moves match { case Nil => false; case h::t => { if(h._1 == move._1 && h._2 == move._2){ return true }else return doesMoveExist(move, t); } } } def main(args: Array[String]) { val sc = new java.util.Scanner (System.in); var n = sc.nextInt(); var i_start = sc.nextInt(); var j_start = sc.nextInt(); var i_end = sc.nextInt(); var j_end = sc.nextInt(); printShortestPath(n, i_start, j_start, i_end, j_end); } }