#!/bin/python import sys ''' UL : [r-2, c-1] UR : [r-2, c+1] R : [r, c+2] LR : [r+2, c+1] LL : [r+2, c-1] L : [r, c-2] ''' allMoves = [] # def checkForFinalPosition(i_end, j_end, moves ): endPt = (i_end,j_end) #returns True if the end point is within 'moves' #return True if len([m for m in moves if moves[m] == endPt]) > 0 else False return [m for m in moves if moves[m] == endPt] # def checkIfMovesHaveBeenUsed(moves): checkedMoves = {} #map(lambda m : checkedMoves[m] = moves[m], [m for m in moves if moves[m] not in allMoves] ) #loop and extract out moves that haven't been made yet #..the knight has already been here for m in moves: if moves[m] not in allMoves: checkedMoves[m] = moves[m] return checkedMoves # def validRedKnightMoves(n, r,c): moves = {} #validate all moves #..UL if r - 2 >=0 and c - 1 >= 0: moves["UL"] = (r-2,c-1) #..UR if r-2 >=0 and c + 1 < n: moves['UR'] = (r-2,c+1) #..R if c + 2 < n: moves["R"] = (r,c+2) #..LR if r + 2 < n and c + 1 < n: moves["LR"] = (r+2,c+1) #..LL if r+2 < n and c - 1 >= 0: moves['LL'] = (r+2,c-1) #..L if c - 2 >= 0: moves["L"] = (r,c-2) #ony care about the moves that HAVE NOT been used yet return checkIfMovesHaveBeenUsed(moves) # i is the row, j is the column def printShortestPath(n, i_start, j_start, i_end, j_end, p): # Print the distance along with the sequence of moves. # Reached the end...Done! if i_start == i_end and j_start == j_end: print len(p) print " ".join(p) return # Find the next possible moves nextMoves = validRedKnightMoves(n,i_start, j_start) #print "nextMoves from (%i,%i): %s" % (i_start,j_start, str(nextMoves) ) #no more moves! if len(nextMoves) == 0: print "Impossible" return #see if any of the next moves are the end point hasEndPt = checkForFinalPosition(i_end,j_end, nextMoves) if len(hasEndPt) == 1: p.append(hasEndPt[0]) print len(p) print " ".join(p) return #track (memoize) allMoves.extend(nextMoves.values()) #loop through all the moves for m in nextMoves: #extend the path nextP = p #append the coord key ('UL','L'...) nextP.append(m) nextCoord = nextMoves[m] #print nextCoord return printShortestPath(n,nextCoord[0],nextCoord[1],i_end, j_end, nextP) #print nextMoves 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, [])