object Solution { type TypeMov = String type Pos = (Int, Int) type Mov = (Pos, TypeMov) val iMov = List(-2, -2, 0, 2, 2, 0); val jMov = List(-1, 1, 2, 1, -1, -2); val nameMov = List("UL", "UR", "R", "LR", "LL", "L"); def findPaths(n: Int, current: List[Mov], end: Pos, visited: Set[Pos]):Array[List[Mov]] = { var solutions = Array.empty[List[Mov]] val lastPos = current.last._1 if(lastPos.equals(end)){ return Array(current); }else{ // Calculate all possible movimentes for(i <- 0 until iMov.size){ val newPos = (lastPos._1 + iMov(i), lastPos._2 + jMov(i)) if(newPos._1 >= 0 && newPos._1 < n && newPos._2 >= 0 && newPos._2 < n && !visited.contains(newPos)){ val newMov: Mov = (newPos, nameMov(i)) val possibleSolutions = findPaths(n, current ::: List(newMov), end, visited + newPos); for(sol <- possibleSolutions) solutions = solutions :+ sol } } } return solutions; } def printShortestPath(n: Int, i_start: Int, j_start: Int, i_end: Int, j_end: Int):Unit = { val solutions = findPaths(n, ((i_start, j_start), "") :: Nil, (i_end, j_end), Set.empty[Pos]) if(solutions.isEmpty) System.out.println("Impossible") else { val shortest = solutions.sortBy(f => f.size).head System.out.println(shortest.size - 1) System.out.println(shortest.tail.map(a => a._2).mkString(" ")) } } 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); } }