object Solution { class node (var row: Int, var col: Int, var depth:Int, var move: String, var parent: node) var myqueue = new scala.collection.mutable.Queue[node] var visited = Array.ofDim[Boolean](200,200) var moves = new Array[(Int,Int,String)](6) var path = new Array[String](200) def printShortestPath(n: Int, i_start: Int, j_start: Int, i_end: Int, j_end: Int): Int = { // Print the distance along with the sequence of moves. // Add the first position to queue val startNode = new node(i_start,j_start,1,"",null) //Moves: UL, UR, R, LR, LL, L moves(0) = (-2,-1,"UL") moves(1) = (-2,1,"UR") moves(2) = (0,2,"R") moves(3) = (2,1,"LR") moves(4) = (2,-1,"LL") moves(5) = (0,-2,"L") //Initialize visited for(i<- 0 to n -1) for(j<-0 to n-1) { visited(i)(j) = false } myqueue.enqueue(startNode) while(!myqueue.isEmpty) { // traverse BFS var curnode = myqueue.dequeue() var row1= 0; var col1 = 0; var row = curnode.row var col = curnode.col var depth = curnode.depth if(!visited(row)(col)) { // visit this node visited(row)(curnode.col) = true // visit nodes in order for(m <- 0 to 5) { row1 = row + moves(m)._1 col1 = col + moves(m)._2 if(row1 <= n - 1 && col1 <= n-1 && row1 >= 0 && col1 >= 0 ) { // valid move if(row1 == i_end && col1 == j_end) { println(depth) // print path for(p<- depth-2 to 0 by -1) { path(p) = curnode.move curnode = curnode.parent } path(depth-1) = moves(m)._3 for(p<-0 to depth -1) { print(path(p) + " ") } println() return 1 } // add to queue path(depth) = moves(m)._3 myqueue.enqueue(new node(row1,col1,depth+1,moves(m)._3,curnode)) } } } } // destination not visited println("Impossible") return 0 } 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); } }