Two Knights
Time limit2sMemory limit1024 MB
Place two knights on a chessboard, move them alternately (any order) to distinct target squares without ever sharing a square, and output the minimum moves plus the actual move sequence, or -1.
- Level
Hard8 of 10
- Topics
- BFS, Graph, Shortest path, Implementation
- Solved
- No attempts yet
Problem
Petya is learning to play chess. He recently noticed that although knights can jump over pieces, they can get in each other's way when reaching the squares they need. Petya placed two knights on the board, one black and one white, and chose a square for each of them where he wants it to end up. Now he wants to know the minimum number of moves the knights need to reach those squares.
Knights move by the rules of chess (one square horizontally and two vertically, or one square vertically and two horizontally). The order of the black knight's and white knight's moves can be arbitrary. The knights are not allowed to stand on the same square at the same time.
Input
The input file contains four squares of the chessboard in the following order: the starting position of the white knight, the starting position of the black knight, the destination of the white knight, the destination of the black knight. A square of the chessboard is given by a file (a letter from a to h) and a rank (a digit from 1 to 8) with no space between them. The descriptions of the squares are separated by one space.
It is guaranteed that the knights start on different squares, and they must also end on different squares.
Output
Output the number of required moves on the first line of the output file. Then output the sequence of moves. A move is described as follows: a letter corresponding to the color of the knight (W for white or B for black) and the square to move to. Output the square in the same format as in the input file.
If the required sequence of moves does not exist, output on the first line of the output file.