#!/bin/ruby def printShortestPath(n, i_start, j_start, i_end, j_end) #UL, UR, R, LR, LL, L i_curr = i_start j_curr = j_start impossible = false moves = 0 path = [] while !impossible && !(i_curr == i_end && j_curr == j_end) moves += 1 if (i_curr - i_end).abs == 1 impossible = true elsif i_curr > i_end # go upper if j_curr >= j_end #UL j_curr -= 1 path << "UL" else #UR j_curr += 1 path << "UR" end i_curr -= 2 elsif i_curr == i_end # stay at row if (j_curr - j_end).abs == 1 impossible = true elsif j_curr < j_end #R j_curr += 2 path << "R" else #L j_curr -= 2 path << "L" end else #go lower i_curr += 2 if j_curr <= j_end #LR j_curr += 1 path << "LR" else #LL j_curr -= 1 path << "LL" end end end if impossible puts "Impossible" else puts moves puts path.join(" ") end 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)