#!/bin/ruby def possible_moves(n, i, j) m = {} m[:UL] = [i - 2, j - 1] if i >= 2 && j >= 1 m[:UR] = [i - 2, j + 1] if i >= 2 && j <= n - 2 m[:R] = [i, j + 2] if j <= n - 3 m[:LR] = [i + 2, j + 1] if i <= n - 3 && j <= n - 2 m[:LL] = [i + 2, j - 1] if i <= n - 3 && j >= 1 m[:L] = [i, j - 2] if j >= 2 m end def bfs(n, start, finish) discovered = { start.join => nil } level_pos = [start] while !level_pos.empty? next_level = [] level_pos.each do |position| moves = possible_moves(n, *position) moves.each do |m, pos| new_pos = pos.join next if discovered.key?(new_pos) discovered[new_pos] = [m, position.join] return discovered if pos == finish next_level << pos end end level_pos = next_level end discovered end def reconstruct_path(discovered, start, finish) next_el = discovered[finish] counter = 0 moves = [] while next_el moves << next_el[0] counter += 1 next_el = discovered[next_el[1]] end { moves: moves, counter: counter } end def printShortestPath(n, i_start, j_start, i_end, j_end) # Print the distance along with the sequence of moves. start = [i_start, j_start] finish = [i_end, j_end] discovered = bfs(n, start, finish) return puts('Impossible') unless discovered.key?(finish.join) res = reconstruct_path(discovered, start.join, finish.join) puts res[:counter] res[:moves].reverse_each { |m| print m.to_s + ' ' } 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)