#!/bin/ruby def get_possible_next_nodes(matrix, n, i_start, j_start, trace) # Possible nodes: [UL, UR, R, LR, LL, L] nodes = Array.new n1 = n-1 # UL node x = i_start - 2 y = j_start - 1 if x.between?(0,n1) && y.between?(0,n1) && matrix[x][y] == false nodes << [trace + " UL", x, y] matrix[x][y] = true end # UR node x = i_start - 2 y = j_start + 1 if x.between?(0,n1) && y.between?(0,n1) && matrix[x][y] == false nodes << [trace + " UR", x, y] matrix[x][y] = true end # R node x = i_start y = j_start + 2 if x.between?(0,n1) && y.between?(0,n1) && matrix[x][y] == false nodes << [trace + " R", x, y] matrix[x][y] = true end # LR node x = i_start + 2 y = j_start + 1 if x.between?(0,n1) && y.between?(0,n1) && matrix[x][y] == false nodes << [trace + " LR", x, y] matrix[x][y] = true end # LL node x = i_start + 2 y = j_start - 1 if x.between?(0,n1) && y.between?(0,n1) && matrix[x][y] == false nodes << [trace + " LL", x, y] matrix[x][y] = true end # L node x = i_start y = j_start - 2 if x.between?(0,n1) && y.between?(0,n1) && matrix[x][y] == false nodes << [trace + " L", x, y] matrix[x][y] = true end nodes end def printShortestPath(n, i_start, j_start, i_end, j_end) # Initiate movable node matrix. Movable to: 1, Unmovable to: 0 matrix = [] (1..n).each do row = [] (1..n).each do row << false end matrix << row end trace = "" matrix[i_start][j_start] = true pool = get_possible_next_nodes(matrix, n, i_start, j_start, trace) found = false result = "" loop do #puts "Pool: #{pool}" new_pool = [] for i in 0..pool.length-1 # check if any node reaching destination if pool[i][1] == i_end && pool[i][2] == j_end found = true result = pool[i][0] # trace break else trace = pool[i][0] new_pool += get_possible_next_nodes(matrix, n, pool[i][1], pool[i][2], trace) end end pool = new_pool break if found || new_pool == [] end if !found puts "Impossible" else result = result.strip puts result.split.length puts result 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)