#!/bin/ruby # Axis: (just so I can remember better) # | # ---------> j # | # | # v i def printShortestPath(n, i, j, i_end, j_end) moves = [] # Actual moves # Moves on both axis until either i==i_end or i==i_end # No need to take priority into consideration here, there's only one direction to go i_dir = ((i_end - i) <=> 0)*2 j_dir = (j_end - j) <=> 0 i_move = { 2 => 'L', -2 => 'U' }.fetch(i_dir, '') j_move = { 1 => 'R', -1 => 'L' }.fetch(j_dir, '') move = i_move + j_move # Could be optimised... while i != i_end && j != j_end do moves << move i += i_dir j += j_dir end # Moves only on the j axis if i == i_end && (j_end - j) % 2 == 1 puts 'Impossible' return end j_dir = ((j_end - j) <=> 0)*2 j_move = { 2 => 'R', -2 => 'L' }.fetch(j_dir, '') # Could be optimised... while i == i_end && j != j_end do moves << j_move j += j_dir end if i == i_end && (j_end - j) % 2 == 1 puts 'Impossible' return end j_dir = ((j_end - j) <=> 0)*2 move = { 2 => 'R', -2 => 'L' }.fetch(j_dir, '') # Could be optimised... while i == i_end && j != j_end do moves << move j += j_dir end # Moves only on the i axis # Has concern for the boundaries # priority: UL UR R LR LL L if j == j_end && (i_end - i) % 4 != 0 puts 'Impossible' return end i_dir = ((i_end - i) <=> 0) while j == j_end && i != i_end do if i_dir == 1 # down if j == 0 moves << 'LL' << 'LR' else moves << 'LR' << 'LL' end i += 4 elsif i_dir == -1 # up if j == n-1 moves << 'UR' << 'UL' else moves << 'UL' << 'UR' end i -= 4 end end puts moves.length puts moves.join(' ') 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 if (i_end - i_start).abs % 2 == 1 # Can't move an odd number on the i axis puts 'Impossible' else printShortestPath(n, i_start, j_start, i_end, j_end) end