#!/bin/python3 import sys """ Author: Dustin Chase Harmon This unweighted graph data structure is a modified version of one that I created. Link to my GitHub where this my Pure-Py-Data-Structures can be found is below https://github.com/D-Chase-H/PurePy-Data-Structures """ class Node(object): """docstring for Node.""" def __init__(self): self.id = None self.edges = set() class Graph(object): """docstring for Graph.""" def __init__(self): self.nodes = dict() ############################################################################ # Insertion Method ############################################################################ def insert_node(self, node_id): try: self.nodes[node_id] except KeyError: new_node = Node() new_node.id = node_id self.nodes[node_id] = new_node return def insert_nodes_from_edge_pair_und(self, pair): """ Undirected insertion of two nodes that both connect to each other pair. pair: list/tuple type == [node_1_id, node_2_id] """ node_1_id = pair[0] self.insert_node(node_1_id) node_1 = self.nodes[node_1_id] node_2_id = pair[1] self.insert_node(node_2_id) node_2 = self.nodes[node_2_id] node_1.edges.add(node_2) node_2.edges.add(node_1) return ############################################################################ # Breadth-First-Search Method ############################################################################ def bfs_shortest_paths(self, start, end): """ start = integer end = integer Returns: Bool """ def determine_path(): nonlocal curr_edges nonlocal visited_nodes nonlocal start_node nonlocal end_node nonlocal depth paths = [[end_node]] complete = False tally = 0 for loop_num in range(depth): remove_nodes = set() new_paths = [] for index, p in enumerate(paths): last_node = p[-1] poss_paths = [] for node in last_node.edges: # If we are on the last node, then skip any edge-node # that is not the start node. if loop_num == depth - 1: if node != start_node: continue if node in visited_nodes: temp = p + [node] poss_paths.append(temp) remove_nodes.add(node) for sub_path in poss_paths: new_paths.append(sub_path) for node in remove_nodes: visited_nodes.remove(node) paths = new_paths paths = [list(reversed(p)) for p in paths] return paths def bfs_check(curr_edges): nonlocal is_connected nonlocal visited_nodes nonlocal end_node nonlocal depth depth += 1 if end_node in curr_edges: is_connected = True return new_edges = set() for node in curr_edges: visited_nodes.add(node) for node_edge in node.edges: if node_edge not in visited_nodes: new_edges.add(node_edge) if not new_edges: return else: bfs_check(new_edges) start_node = self.nodes[start] end_node = self.nodes[end] if start_node == end_node: return [[start_node]] depth = 0 visited_nodes = set([start_node]) curr_edges = set([edg for edg in start_node.edges]) is_connected = False bfs_check(curr_edges) paths = determine_path() return paths ################################################################################ def printShortestPath(n, i_start, j_start, i_end, j_end): def get_coords(n): temp = [] for i in range(n): for j in range(n): pair = (i, j) temp.append((i, j)) return temp def find_connections(n, coord): def connection_check(coord, new_coord): nonlocal relevant_nodes pair = (coord, new_coord) rev_pair = (new_coord, coord) if pair not in relevant_nodes and rev_pair not in relevant_nodes: relevant_nodes.add(pair) return i, j = coord if j - 2 >= 0: left = (i, j - 2) connection_check(coord, left) if j - 1 >= 0: if i - 2 >= 0: up_left = (i - 2, j - 1) connection_check(coord, up_left) if i + 2 <= n - 1: down_left = (i + 2, j - 1) connection_check(coord, down_left) if j + 2 <= n - 1: right = (i, j + 2) connection_check(coord, right) if j + 1 <= n - 1: if i - 2 >= 0: up_right = (i - 2, j + 1) connection_check(coord, up_right) if i + 2 <= n - 1: down_right = (i + 2, j + 1) connection_check(coord, down_right) return def coords_to_dirction(node1, node2): i, j = node1.id coord2 = node2.id left = (i, j - 2) if coord2 == left: return "L" up_left = (i - 2, j - 1) if coord2 == up_left: return "UL" down_left = (i + 2, j - 1) if coord2 == down_left: return "LL" right = (i, j + 2) if coord2 == right: return "R" up_right = (i - 2, j + 1) if coord2 == up_right: return "UR" down_right = (i + 2, j + 1) if coord2 == down_right: return "LR" relevant_nodes = set() coords = get_coords(n) start_coord = (i_start, j_start) target_coord = (i_end, j_end) for coord in coords: find_connections(n, coord) g = Graph() for i, j in relevant_nodes: pair = (i, j) g.insert_nodes_from_edge_pair_und(pair) try: g.nodes[target_coord] except KeyError: print("Impossible") return shortest_paths = g.bfs_shortest_paths(start_coord, target_coord) priority = {"UL":1, "UR":2, "R":3, "LR":4, "LL":5, "L":6} if not shortest_paths: print("Impossible") return else: total_paths = len(shortest_paths) index = 0 temp_paths = [] while shortest_paths: sub = shortest_paths.pop() temp = [] for sub_index, coord1 in enumerate(sub): try: coord2 = sub[sub_index + 1] temp.append(coords_to_dirction(coord1, coord2)) except IndexError: break temp_paths.append(temp) shortest_paths = temp_paths path_len = len(shortest_paths[0]) while index < path_len - 1: if len(shortest_paths) == 1: break remove_indicies = set() best_direction = None for num in range(len(shortest_paths)): direct = shortest_paths[num][index] if best_direction is None: best_direction = direct else: if priority[direct] < priority[best_direction]: best_direction = direct for num in range(len(shortest_paths)): direct = shortest_paths[num][index] if direct != best_direction: remove_indicies.add(num) shortest_paths = [p for ind, p in enumerate(shortest_paths) if ind not in remove_indicies] index += 1 print(path_len) print(' '.join(shortest_paths[0])) return 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)