package main import "fmt" var board [][]bool var n, targetX, targetY int type variant struct { x, y int path []int } func bfs(x, y int) ([]int, bool) { ways := make([]variant, 0) ways = append(ways, variant{x, y, []int{}}) for len(ways) > 0 { newWays := make([]variant, 0) for _, way := range ways { for i := 0; i < 6; i++ { var newX, newY int switch i { case 0: newX, newY = way.x - 2, way.y - 1 case 1: newX, newY = way.x - 2, way.y + 1 case 2: newX, newY = way.x, way.y + 2 case 3: newX, newY = way.x + 2, way.y + 1 case 4: newX, newY = way.x + 2, way.y - 1 case 5: newX, newY = way.x, way.y - 2 } if newX >= 0 && newX < n && newY >= 0 && newY < n && !board[newX][newY] { newPath := make([]int, len(way.path)) copy(newPath, way.path) newPath = append(newPath, i) if newX == targetX && newY == targetY { return newPath, true } newWays = append(newWays, variant{newX, newY, newPath}) board[newX][newY] = true } } } ways = newWays } return make([]int, 0), false } func main() { fmt.Scanf("%d", &n) board = make([][]bool, n) for i := 0; i < n; i++ { board[i] = make([]bool, n) } var startX, startY int fmt.Scanf("%d %d %d %d", &startX, &startY, &targetX, &targetY) board[startX][startY] = true path, possible := bfs(startX, startY) if !possible { fmt.Print("Impossible") } else { fmt.Println(len(path)) for i := 0; i < len(path); i++ { switch path[i] { case 0: fmt.Print("UL ") case 1: fmt.Print("UR ") case 2: fmt.Print("R ") case 3: fmt.Print("LR ") case 4: fmt.Print("LL ") case 5: fmt.Print("L ") } } } }