package main import ( "fmt" "strings" ) const no = "Impossible" func abs(i int) int { if i < 0 { return i * -1 } return i } func main() { var n, startRow, startCol, endRow, endCol int if _, err := fmt.Scanln(&n); err != nil { fmt.Println("Couldnt scan n") } if _, err := fmt.Scanln(&startRow, &startCol, &endRow, &endCol); err != nil { fmt.Println("Couldnt scan n") } //n = 7 //startRow, startCol, endRow, endCol = 2, 2, 6, 3 // Ensure all points on the board if startRow > n || startCol > n || endRow > n || endCol > n { fmt.Println(no) } ok, _, _ := possible(startRow, startCol, endRow, endCol) if !ok { fmt.Println(no) return } curRow, curCol := startRow, startCol var moves []string for { move := decideMove(curRow, curCol, endRow, endCol, n) ok, nextRow, nextCol := doMove(move, curRow, curCol, n) if !ok { fmt.Println("doMove !ok", move) } // Record the move curRow, curCol = nextRow, nextCol moves = append(moves, move) if curRow == endRow && curCol == endCol { break } } fmt.Println(len(moves)) fmt.Println(strings.Join(moves, " ")) } func decideMove(curRow, curCol, endRow, endCol, n int) string { udDelta := endRow - curRow lrDelta := endCol - curCol if udDelta < 0 { // prefer UL to UR if curCol-1 >= 0 && lrDelta <= 0 { // ensure we dont move off the board to the left return "UL" } else { return "UR" // We'll move up and right away from the left border } } else if udDelta == 0 && lrDelta > 0 { // Next, prefer R return "R" } else if udDelta > 0 { // Next Prefer LR, LL if curCol+1 < n && lrDelta >= 0 { // ensure we dont move of the board to the right return "LR" } else { return "LL" } } else if udDelta == 0 && lrDelta < 0 { // Finally L return "L" } fmt.Println("PANIC!! no valid move?!?", curRow, curCol, endRow, endCol, n) return "" } func doMove(move string, curRow, curCol, n int) (ok bool, nextRow, nextCol int) { switch move { case "UL": if curRow-2 < 0 || curCol-1 < 0 { return false, 0, 0 } return true, curRow - 2, curCol - 1 case "UR": if curRow-2 < 0 || curCol+1 >= n { return false, 0, 0 } return true, curRow - 2, curCol + 1 case "R": if curCol+2 >= n { return false, 0, 0 } return true, curRow, curCol + 2 case "LR": if curRow+2 >= n || curCol+1 >= n { return false, 0, 0 } return true, curRow + 2, curCol + 1 case "LL": if curRow+2 >= n || curCol-1 < 0 { return false, 0, 0 } return true, curRow + 2, curCol - 1 case "L": if curCol-2 < 0 { return false, 0, 0 } return true, curRow, curCol - 2 } // fmt.Println("PANIC, invalid move given", move) return false, 0, 0 } func possible(curRow, curCol, endRow, endCol int) (ok bool, updownMoves, leftRightMoves int) { udDelta := abs(endRow - curRow) if (udDelta % 2) == 1 { // We can only move up/down in 2s return false, updownMoves, leftRightMoves } updownMoves = udDelta / 2 // Left/Right moves are (delta - updownMoves) / 2 lrDelta := abs(endCol - curCol) if lrDelta < 0 { lrDelta *= -1 } if (abs(lrDelta-updownMoves) % 2) == 1 { // After up/down we can only move L/R in 2s return false, updownMoves, leftRightMoves } leftRightMoves = (lrDelta - updownMoves) / 2 // TODO this isnt always correct //fmt.Println("Its possible with updownMoves=", updownMoves, "and leftRightMoves=", leftRightMoves) return true, updownMoves, leftRightMoves }