#!/bin/python3 from collections import deque import sys INF = 200 * 200 + 200 class Space(object): def __init__(self): self.distance = INF self.how_connected = "X" self.processed = False self.connected_from = None def printShortestPath(n, i_start, j_start, i_end, j_end): # Create a board, which contains n x n Spaces board = [[Space() for j in range(n)] for i in range(n)] # Fill in the values for the starting node current_space = board[i_start][j_start] current_space.processed = True current_space.distance = 0 current_space.how_connected = "ST" current_i = i_start current_j = j_start # Fill in the values for the connected spaces using # something akin to Djikstra's keep_going = True while keep_going: # Check UL test_i = current_i - 2 test_j = current_j - 1 if test_i < n and test_i >= 0 and test_j < n and test_j >=0: if board[test_i][test_j].processed == False: if board[test_i][test_j].distance > current_space.distance + 1: board[test_i][test_j].distance = current_space.distance + 1 board[test_i][test_j].how_connected = "UL" board[test_i][test_j].connected_from = board[current_i][current_j] # Check UR test_i = current_i - 2 test_j = current_j + 1 if test_i < n and test_i >= 0 and test_j < n and test_j >=0: if board[test_i][test_j].processed == False: if board[test_i][test_j].distance > current_space.distance + 1: board[test_i][test_j].distance = current_space.distance + 1 board[test_i][test_j].how_connected = "UR" board[test_i][test_j].connected_from = board[current_i][current_j] # Check L test_i = current_i test_j = current_j - 2 if test_i < n and test_i >= 0 and test_j < n and test_j >=0: if board[test_i][test_j].processed == False: if board[test_i][test_j].distance > current_space.distance + 1: board[test_i][test_j].distance = current_space.distance + 1 board[test_i][test_j].how_connected = "L" board[test_i][test_j].connected_from = board[current_i][current_j] # Check R test_i = current_i test_j = current_j + 2 if test_i < n and test_i >= 0 and test_j < n and test_j >=0: if board[test_i][test_j].processed == False: if board[test_i][test_j].distance > current_space.distance + 1: board[test_i][test_j].distance = current_space.distance + 1 board[test_i][test_j].how_connected = "R" board[test_i][test_j].connected_from = board[current_i][current_j] # Check LL test_i = current_i + 2 test_j = current_j - 1 if test_i < n and test_i >= 0 and test_j < n and test_j >=0: if board[test_i][test_j].processed == False: if board[test_i][test_j].distance > current_space.distance + 1: board[test_i][test_j].distance = current_space.distance + 1 board[test_i][test_j].how_connected = "LL" board[test_i][test_j].connected_from = board[current_i][current_j] # Check LR test_i = current_i + 2 test_j = current_j + 1 if test_i < n and test_i >= 0 and test_j < n and test_j >=0: if board[test_i][test_j].processed == False: if board[test_i][test_j].distance > current_space.distance + 1: board[test_i][test_j].distance = current_space.distance + 1 board[test_i][test_j].how_connected = "LR" board[test_i][test_j].connected_from = board[current_i][current_j] current_space.processed = True # Find the next space to start with current_min_distance = INF # Find all spaces that are of the minimum distance away from the current # space. potential_next = [] for i in range(n): for j in range(n): if board[i][j].processed == False: if board[i][j].distance < current_min_distance: current_min_distance = board[i][j].distance current_i = i current_j = j current_space = board[i][j] potential_next = [] potential_next.append((i, j, board[i][j].how_connected)) elif board[i][j].distance == current_min_distance: potential_next.append((i, j, board[i][j].how_connected)) # If potential_next is not empty, there were ties for the minimum distance. if len(potential_next) > 1: how_connected_dict = {} for each in potential_next: if each[2] == "UL": how_connected_dict["UL"] = (each[0], each[1]) elif each[2] == "UR": how_connected_dict["UR"] = (each[0], each[1]) elif each[2] == "R": how_connected_dict["R"] = (each[0], each[1]) elif each[2] == "LR": how_connected_dict["LR"] = (each[0], each[1]) elif each[2] == "LL": how_connected_dict["LL"] = (each[0], each[1]) else: how_connected_dict["L"] = (each[0], each[1]) if "UL" in how_connected_dict: current_i = how_connected_dict["UL"][0] current_j = how_connected_dict["UL"][1] current_space = board[current_i][current_j] elif "UR" in how_connected_dict: current_i = how_connected_dict["UR"][0] current_j = how_connected_dict["UR"][1] current_space = board[current_i][current_j] elif "R" in how_connected_dict: current_i = how_connected_dict["R"][0] current_j = how_connected_dict["R"][1] current_space = board[current_i][current_j] elif "LR" in how_connected_dict: current_i = how_connected_dict["LR"][0] current_j = how_connected_dict["LR"][1] current_space = board[current_i][current_j] elif "LL" in how_connected_dict: current_i = how_connected_dict["LL"][0] current_j = how_connected_dict["LL"][1] current_space = board[current_i][current_j] elif "L" in how_connected_dict: current_i = how_connected_dict["L"][0] current_j = how_connected_dict["L"][1] current_space = board[current_i][current_j] if current_space.distance == INF: keep_going = False print("Impossible") elif current_space == board[i_end][j_end]: keep_going = False print(current_space.distance) traceback_list = deque() traceback_list.append(current_space.how_connected) prior_space = current_space.connected_from while True: traceback_list.append(prior_space.how_connected) prior_space = prior_space.connected_from if prior_space.distance == 0: break traceback_in_order = [] while traceback_list: traceback_in_order.append(traceback_list.pop()) print(' '.join(traceback_in_order)) 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)