#!/bin/ruby @cache = {} @visited = {} # UL, UR, R, LR, LL, L def next_moves_for(i,j,i_end,j_end) moves = [] moves << [i-2,j-1,'UL'] if i > i_end moves << [i-2,j+1,'UR'] if i > i_end moves << [i,j+2,'R'] if j < j_end moves << [i+2,j+1,'LR'] if i < i_end moves << [i+2,j-1,'LL'] if i < i_end moves << [i,j-2,'L'] if j > j_end return moves end def printShortestPath(n, i_start, j_start, i_end, j_end,path = []) if @cache[[i_start,j_start]] return @cache[[i_start,j_start]] elsif i_start == i_end && j_start == j_end return [[],true] elsif i_start < 0 || j_start < 0 || i_start > (n-1) || j_start > (n-1) return [[],false] else found = false min_pth = [] min_len = 10**10 next_moves = next_moves_for(i_start,j_start,i_end,j_end) next_moves.each do |move_i,move_j,move_type| if !path.include?([move_i,move_j]) path1 = path.clone path1 << [move_i,move_j] pth,res = printShortestPath(n,move_i,move_j,i_end,j_end,path1) pth1 = pth.clone pth1 << move_type found ||= res if res && pth1.length < min_len min_pth = pth1 min_len = pth1.length end end end @cache[[i_start,j_start]] = [min_pth,found] return @cache[[i_start,j_start]] 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 @path,res = printShortestPath(n, i_start, j_start, i_end, j_end) if res puts @path.length puts @path.reverse.join(" ") else puts "Impossible" end