#!/bin/ruby def move_left(n, i_s, j_s, i_e, j_e) return ["L"] * ((j_s - j_e) / 2) end def move_right(n, i_s, j_s, i_e, j_e) return ["R"] * ((j_e - j_s) / 2) end def move_down(n, i_s, j_s, i_e, j_e) if i_s == i_e if j_s > j_e return move_left(n, i_s, j_s, i_e, j_e) elsif j_s < j_e return move_right(n, i_s, j_s, i_e, j_e) else return [] end elsif j_s + (i_e - i_s)/2 < j_e return ["R"] + move_down(n, i_s, j_s + 2, i_e, j_e) elsif 2 * (j_s - j_e) < (i_e - i_s) return ["LR"] + move_down(n, i_s + 2, j_s + 1, i_e, j_e) else return ["LL"] + move_down(n, i_s + 2, j_s - 1, i_e, j_e) end end def move_up(n, i_s, j_s, i_e, j_e) if i_s == i_e if j_s > j_e return move_left(n, i_s, j_s, i_e, j_e) elsif j_s < j_e return move_right(n, i_s, j_s, i_e, j_e) else return [] end elsif 2 * (j_e - j_s) < (i_s - i_e) return ["UL"] + move_up(n, i_s - 2, j_s - 1, i_e, j_e) else return ["UR"] + move_up(n, i_s - 2, j_s + 1, i_e, j_e) end end def printShortestPath(n, i_start, j_start, i_end, j_end) i_s,j_s,i_e,j_e = i_start,j_start,i_end,j_end if (i_start - i_end).abs % 2 == 1 puts "Impossible" return elsif (i_start - i_end).abs % 4 == 2 && ((j_start - j_end).abs % 4 == 0 || (j_start - j_end).abs % 4 == 2) puts "Impossible" return elsif (i_start - i_end).abs % 4 == 0 && ((j_start - j_end).abs % 4 == 1 || (j_start - j_end).abs % 4 == 3) puts "Impossible" return end r = [] if (i_start > i_end) r = move_up(n, i_s, j_s, i_e, j_e) elsif (i_start < i_end) r = move_down(n, i_s, j_s, i_e, j_e) elsif (j_start > j_end) r = move_left(n, i_s, j_s, i_e, j_e) else r = move_right(n, i_s, j_s, i_e, j_e) end puts r.length puts r*" " end n = gets.strip.to_i i_start, j_start, i_end, j_end = gets.strip.split(' ') i_start = i_start.to_i j_start = j_start.to_i i_end = i_end.to_i j_end = j_end.to_i printShortestPath(n, i_start, j_start, i_end, j_end)