#!/bin/ruby UL = 'UL'.freeze UR = 'UR'.freeze R = 'R'.freeze LR = 'LR'.freeze LL = 'LL'.freeze L = 'L'.freeze B_ARRAY = [].freeze Space = ' '.freeze MOVEMENT_HASH= { true => { true => LR, false => LL, }, false => { true => UR, false => UL, } } MULTIMOVEMENT_HASH= { true => { true => [R,LR], false => [LR,LL], }, false => { true => [UL,UR], false => [UL], } } def printShortestPath(n, i_start, j_start, i_end, j_end) i_diff = i_end - i_start if i_diff % 2 == 0 && (j_diff = j_end - j_start) % 2 == (i_diff % 4 == 0 ? 0 : 1 ) path = shortestPath(n,i_start, j_start, i_end, j_end) puts path.size puts path.join(Space) else puts "Impossible" end end def shortestPath(n, i_start, j_start, i_end, j_end) i_step = i_end - i_start j_step = j_end - j_start if i_step == 0 && j_step == 0 B_ARRAY elsif i_step == 0 steps = j_step / 2 if steps > 0 Array.new(steps) {R} else Array.new(-steps) {L} end elsif j_step == 0 steps = i_step / 2 p_move = np_move = nil max_step = end_block = 0 if steps > 0 p_move = LR np_move = LL max_step = steps / 2 end_block = n - (j_start) else p_move = UL np_move = UR max_step = (steps / 2).abs end_block = j_start end arr = [] end_block = max_step if end_block >= max_step end_block.times { arr << p_move } (max_step - end_block).times{ arr.push(np_move, p_move)} end_block.times { arr << np_move } arr elsif j_step.abs * 2 == i_step.abs move = MOVEMENT_HASH[i_step > 0][j_step > 0] Array.new(j_step.abs) {move} else moves = MULTIMOVEMENT_HASH[i_step > 0][j_step > 0] slope = (i_step.to_f / j_step).abs move = if ((moves[1] == LR) && slope > 2) || ((moves[1] == UR || moves[1] == LL) && slope < 2) moves[1] else moves[0] end if move == R j_start += 2 else i_start +=(move == UL || move == UR) ? -2 : 2 j_start +=(move == UL || move == LL) ? -1 : 1 end [move].push *shortestPath(n, i_start, j_start, i_end, j_end) 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)