#!/bin/python3 import sys class Move: def __init__(self, next_i, next_j, move_name): self.pos_i = next_i self.pos_j = next_j self.move_name = move_name def __repr__(self): return "{}:{},{}".format(self.move_name, self.pos_i, self.pos_j) def printShortestPath(n, i_start, j_start, i_end, j_end): # Print the distance along with the sequence of moves. if not is_valid(n, i_start, j_start, i_end, j_end): print("Impossible") return result = get_shortest_path(n, i_start, j_start, i_end, j_end) # Sort result moves in order of priority priorities = { "UL": 1, "UR": 2, "R": 3, "LR": 4, "LL": 5, "L": 6, } result = [(priorities[n], n) for n in result] result.sort() result = [n[1] for n in result] print(len(result)) print(" ".join(result)) def UL(curr_i, curr_j, last_move=None): return Move(curr_i - 2, curr_j - 1, "UL") def UR(curr_i, curr_j, last_move=None): return Move(curr_i - 2, curr_j + 1, "UR") def R(curr_i, curr_j, last_move=None): return Move(curr_i, curr_j + 2, "R") def LR(curr_i, curr_j, last_move=None): return Move(curr_i + 2, curr_j + 1, "LR") def LL(curr_i, curr_j, last_move=None): return Move(curr_i + 2, curr_j - 1, "LL") def L(curr_i, curr_j, last_move=None): return Move(curr_i, curr_j - 2, "L") def in_bounds(move, n): """ True if move within board bounds """ # 0 <= i,j < n return 0 <= move.pos_i < n and 0 <= move.pos_j < n def generate_valid_moves(curr_i, curr_j, n): """ Generates an array of next moves. """ moves = [f(curr_i, curr_j) for f in [UL, UR, R, LR, LL, L]] return [m for m in moves if in_bounds(m, n)] def get_shortest_path(n, i_start, j_start, i_end, j_end): """ Returns a sequence of steps for getting a shortest path. Assumes there must be a valid shortest path. Step priority is: UL, UR, R, LR, LL, L Algorithm is greedy """ curr_i = i_start curr_j = j_start current_distance = abs(i_end - curr_i) + abs(j_end - curr_j) path = [] while current_distance != 0: next_moves = [(abs(i_end - m.pos_i) + abs(j_end - m.pos_j), m) for m in generate_valid_moves(curr_i, curr_j, n)] min_dist = next_moves[0][0] min_move = next_moves[0][1] for (dist, m) in next_moves: if dist < min_dist: min_dist = dist min_move = m current_distance = min_dist path.append(min_move.move_name) curr_i = min_move.pos_i curr_j = min_move.pos_j return path def is_valid(n, i_start, j_start, i_end, j_end): """ Returns if a path exists. @returns: bool """ if abs(i_end - i_start) % 2 == 1: return False if abs(i_end - i_start) % 4 == 0 and abs(j_end - j_start) % 2 == 0: return True if abs(i_end - i_start) % 4 == 2 and abs(j_end - j_start)% 2 == 1: return True return False if __name__ == "__main__": 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)] printShortestPath(n, i_start, j_start, i_end, j_end)