#!/bin/python3 import sys def is_valido(n,p): (i,j) = p return i>=0 and j>=0 and i < n and j menorc: return [] if chegou_ao_fim([(ls,cs)],(le,ce)): return caminho dist = distancia(ls,cs,le,ce) if menorc != -1 and dist > (max): return [] elif menorc == -1 and dist > min + 10*(max): #print(dist,min,max) return [] possibilities = all_move(board,ls,cs) if dist < min or min == -1: # print('new',dist,min,max) min = dist if dist > 5: possibilities = reordena(possibilities,le,ce) resp,fim = [] , False for p in (possibilities): total += 1 bc = [row[:] for row in board] ca = caminho[:] atual = shortpath(p[0],p[1],le,ce,bc,ca,cont+1,menorc,min,max) if chegou_ao_fim(atual,(le,ce)): # print(min) fim = True if len(atual) < menorc or menorc == -1: menorc = len(atual) resp.append(atual) if fim: menor, pos = len(resp[0]),0 for p,r in enumerate(resp): if len(r) < len(resp[pos]): menor, pos = len(r),p return resp[pos] return [] def make_board(n): line = [0 for i in range(n)] b = [line[:] for j in range(n)] return b def direction(pre,pos,b): i = pre[0] j = pre[1] pob = [(i-2,j-1),(i-2,j+1),(i,j+2),(i+2,j+1),(i+2,j-1),(i,j-2)] directions = ['UL','UR','R','LR','LL','L'] for i,p in enumerate(pob): if pos == p: return directions[i] return "X" def path(x,b): pre = x.pop(0) resp = [] for pos in x: resp.append(direction(pre,pos,b)) pre = pos return resp def print_result(x,b): if len(x) == 0: print('Impossible') else: print("{}\n{}".format(len(x)-1," ".join(path(x,b)))) def printShortestPath(n, ls, cs, le, ce): b = make_board(n) max = n**(1/11)+2 x = shortpath(ls,cs,le,ce,b,[],1,-1,-1,max) #print('max',max) print_result(x,b) def le_dados(): n = int(input().strip()) i_start, j_start, i_end, j_end = input().strip().split(' ') i_start, j_start, i_end, j_end = [int(i_start), int(j_start), int(i_end), int(j_end)] return n, i_start, j_start, i_end, j_end def teste(): import time import red_knight_dados_teste as r x = time.time() z = r.le_dados8 n, i_start, j_start, i_end, j_end = z() printShortestPath(n, i_start, j_start, i_end, j_end) y = time.time() print() print(y-x) print(__file__, "teste()",z.__name__) def main(): n, i_start, j_start, i_end, j_end = le_dados() printShortestPath(n, i_start, j_start, i_end, j_end) if __name__ == "__main__": main()