Traveling Queen Problem#2530
Black has been defeated and the white army has won, but unfortunately, the white king was killed in the battle. Therefore, the white queen is searching for a new mate. She is unsure which of the knights to marry and decides to visit them all. Afterwards, she plans to visit the bishop to arrange the marriage.
Given a chessboard with its current state, find the minimal number of moves required for the queen to visit every knight and finally visit the bishop.
The queen visits by standing on one of the (at most) eight neighbouring squares; she does not have to move between two visits. For each move, the queen can go any number of squares in one of the eight directions (horizontal, vertical, or diagonal). No move may pass through or stop at a non-empty square.
The first line contains the number of scenarios. Each scenario consists of a chessboard description. The rows 8, \ldots, 1 are given in this order, one line per row. Each line contains characters to represent the squares at columns a, \ldots, h of that row. Each description is followed by an empty line.
There is one character to denote the starting position of the queen, and one to denote the square where the bishop stands. There is any number of pawns, given as , who simply block movement, as well as – knights denoted as . All other squares are given as and are empty.
For every scenario, output begins with a line containing "Scenario #:", where is the number of the scenario starting at .
Then print the lexicographically first path that contains the minimal number of moves, ends adjacent to the bishop, and visits each knight at least once. The path should be given in a single line by concatenating the names of the squares where the queen stands, in order. Each square name consists of a lowercase letter followed by a decimal digit. If no such path exists, output "" on a single line. Terminate the output for the scenario with a blank line.
Example 1