object Solution { // Order UL, UR, R, LR, LL, L def legal(n: Int)(move: ((Int, Int), String)): Boolean = { val ((i, j), _) = move (i >= 0 && i < n && j >= 0 && j < n) } def moves(i: Int, j: Int): Stream[((Int, Int), String)] = Stream(((i - 2, j - 1), "UL"), ((i - 2, j - 1), "UR"), ((i, j + 2), "R"), ((i + 2, j + 1), "LR"), ((i + 2, j - 1), "LL"), ((i, j - 2), "L")) def legalMoves(n: Int)(i: Int, j: Int): Stream[((Int, Int), String)] = { moves(i, j).filter(legal(n)) } def movesWithHistory(n: Int)(i: Int, j: Int, hist: List[String]): Stream[((Int, Int), List[String])] = { legalMoves(n)(i, j).map(m => (m._1, m._2 :: hist)) } def newMoves(n: Int)(i: Int, j: Int, hist: List[String], old: Set[(Int, Int)]): Stream[((Int, Int), List[String])] = { movesWithHistory(n)(i, j, hist).filter(mv => !(old contains mv._1)) } def from(n: Int)(init: Stream[((Int, Int), List[String])], old: Set[(Int, Int)]): Stream[((Int, Int), List[String])] = { if (init.isEmpty) Stream() else { val more = init.flatMap(i => newMoves(n)(i._1._1, i._1._2, i._2, old)) init #::: from(n)(more, old ++ more.map(_._1)) } } def PrintShortestPath(n: Int, i_start: Int, j_start: Int, i_end: Int, j_end: Int) = { lazy val valid = from(n)(Stream(((i_start, j_start), Nil)), Set()).filter(x => x._1._1 == i_end && x._1._2 == j_end) if (valid.isEmpty) println("Impossible") println(valid.head._2.length) println(valid.head._2.reverse.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); } }