import sys class graph(object): """unweighted directed graph """ def __init__(self): """set _vmap to and _vprev an empty python dict all vertex are represented by a simple index _vmap: {vertex x: x's adjacency list} _vprev: {vertex x: x's prev vertex computed by bfs routine} """ self._vmap = {}; self._vprev = {}; def add_edge(self, start, end): """add an edge to the graph """ if self._vmap.has_key(start): self._vmap[start].append(end) else: self._vmap[start] = [end] def bfs_shortest(self, start): """one-source shortest-path algorithm """ queue = [start] self._vprev[start] = None while len(queue) != 0: v = queue[0] queue.pop(0) if self._vmap.has_key(v): v_adj = self._vmap[v] else: continue for nextv in v_adj: if self._vprev.has_key(nextv):# and self._vprev[nextv] is not None: # nextv has already found its parent"" continue else: queue.append(nextv) self._vprev[nextv] = v def get_path(self, end): """return the shortest path as a python list """ v = end; path = [] while self._vprev.has_key(v) and self._vprev[v] is not None: path.insert(0, v) v = self._vprev[v] if self._vprev.has_key(v): path.insert(0, v) # insert the start point to the path else: print "Impossible" sys.exit() return path class chessboard(object): """a chessboard of size n*n class """ def __init__(self, n): self._size = n self._board = graph() #next_point = ((-2,-1),(-2,1),(0,2),(2, 1),(2,-1),(0,-2)) next_point = ((2, 1), (2,-1), (0,-2), (-2,1), (-2,-1), (0,2)) #self.dic = {(-2,-1):'LL',(-2,1):'LR',(0,2):'L',(2, 1):'UL',(2,-1):'UR',(0,-2):'R'} self.dic = {(2, 1):'UL', (2,-1):'UR', (0,-2):'R', (-2,1):'LR', (-2,-1):'LL', (0,2):'L'} ''' next_point = ((2, 1), (2, -1), \ (1, 2), (1, -2), \ (-2, 1), (-2, -1), \ (-1, 2), (-1, -2)) ''' for x in range(n): for y in range(n): start = self.point2index(x, y) for dx, dy in next_point: nx = x + dx ny = y + dy if self.is_valid(nx, ny): end = self.point2index(nx, ny) self._board.add_edge(start, end) def is_valid(self, x, y): """whether or not point (x, y) is valid in the chessboard """ return 0 <= x < self._size and 0 <= y < self._size def point2index(self, x, y): """convert a chessboard point to the internal graph vertex index """ return x * self._size + y def index2point(self, p): """convert the internal graph vertex index back to a chessboard point """ return (p / self._size, p % self._size) def solve_knight(self, x, y, x1, y1): start = self.point2index(x, y) end = self.point2index(x1, y1) self._board.bfs_shortest(start) path = [self.index2point(x) for x in self._board.get_path(end)] print len(path) - 1 c = len(path) - 1 printlist = list() for i in range(0 , c): d = tuple(x-y for x, y in zip(path[i], path[i+1])) printlist.insert(0, self.dic[d]) print(" ".join(str(x) for x in printlist)) def printShortestPath(n, i_start, j_start, i_end, j_end): chess = chessboard(n) chess.solve_knight(i_start, j_start, i_end, j_end) return 0 if __name__ == "__main__": n = int(raw_input().strip()) i_start, j_start, i_end, j_end = raw_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)