#!/bin/ruby require 'thread' def printShortestPath(n, i_start, j_start, i_end, j_end) grid = Array.new(n) { Array.new(n, 0) } prev = Array.new(n) { Array.new(n) } queue = Queue.new queue.enq [i_start, j_start] grid[i_start][j_start] = 1 while !queue.empty? i, j = queue.deq x, y = i-2, j-1 if x > -1 && y > -1 && grid[x][y] == 0 grid[x][y] = 1 prev[x][y] = [i, j, 'UL'] queue.enq [x, y] end x, y = i-2, j+1 if x > -1 && y < n && grid[x][y] == 0 grid[x][y] = 1 prev[x][y] = [i, j, 'UR'] queue.enq [x, y] end x, y = i, j+2 if y < n && grid[x][y] == 0 grid[x][y] = 1 prev[x][y] = [i, j, 'R'] queue.enq [x, y] end x, y = i+2, j+1 if x < n && y < n && grid[x][y] == 0 grid[x][y] = 1 prev[x][y] = [i, j, 'LR'] queue.enq [x, y] end x, y = i+2, j-1 if x < n && y > -1 && grid[x][y] == 0 grid[x][y] = 1 prev[x][y] = [i, j, 'LL'] queue.enq [x, y] end x, y = i, j-2 if y > -1 && grid[x][y] == 0 grid[x][y] = 1 prev[x][y] = [i, j, 'L'] queue.enq [x, y] end end # Print the distance along with the sequence of moves. if grid[i_end][j_end] == 1 len = 0 path = '' i, j = i_end, j_end while prev[i][j] path = ' ' + prev[i][j][2] + path i, j = prev[i][j] len += 1 end puts len else path = 'Impossible' end puts path.strip end n = gets.strip.to_i i_start, j_start, i_end, j_end = gets.strip.split(' ').map(&:to_i) printShortestPath(n, i_start, j_start, i_end, j_end)