#!/bin/ruby def printShortestPath(n, i_start, j_start, i_end, j_end) res = bfs(n, i_start, j_start, i_end, j_end) if res.empty? puts 'Impossible' else puts res.count puts res.join(' ') end end def bfs(n, j_start, i_start, j_end, i_end) visited = {} queue = [] queue.push([i_start, j_start, []]) visited[[i_start, j_start]] = true while !queue.empty? i, j, directions = queue.shift return directions if i == i_end && j == j_end pairs(n, i, j).each do |direction, child_node| next if visited[child_node] || !child_node queue.push([*child_node, directions + [direction]]) visited[child_node] = true end end [] end def pairs(n, x, y, i = 1, j = 2) { UL: chk_brd(n, x - i, y - j), UR: chk_brd(n, x + i, y - j), R: chk_brd(n, x + j, y), LR: chk_brd(n, x + i, y + j), LL: chk_brd(n, x - i, y + j), L: chk_brd(n, x - j, y) } end def chk_brd(n, x, y) return if !(x >= 0 && y >= 0 && x <= n && y <= n) [x, y] 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)