KNIGHTSG - KNIGHTS level testing
The image above is an example of a level in Arzola's videogame 'KNIGHTS'. The rules are very simple. The player is given a chess board, where each square is either empty, contains a wall, or contains a knight of one of three colours. Some squares are also marked with a colour - the player beats the level if all marked squares contain a knight of their respective colour at the same time. To accomplish this, the player can select any knight and place him on an empty square using the classic chess knight move (2 squares in one direction, 1 square in a direction perpendicular to the first).
You will help test a few new level designs for this game. Given a starting configuration and several goal configurations (depicting which squares contain which knight), find the minimum number of moves required to get to those goal configurations.
The first line contains two integers 1 ≤ r,c < 24.
The following r lines contain c characters each, describing the starting configuration of the level. The characters in the grid will be '#' for wall, '.' for an empty square, and 'R', 'B' and 'Y' for a red, blue and yellow knight, respectively. The number of squares that are not walls will be at most 12.
A blank line follows, followed by a line with an integer 1 ≤ q ≤ 75,000 - the number of suggested goal configurations for this level. You may assume that q*r*c ≤ 106.
q descriptions of goal configurations follow, separated by blank lines. Each description will be r rows consisting of c characters, from the same set as the starting configuration. You may assume that the walls are at the same places as in the starting configuration, and that the number of knights of each colour is the same as the number of knights of that colour in the starting configuration.
For each suggested goal configuration, if it is not reachable from the starting configuration in any number of moves, output -1.
Otherwise, output the minimum number of moves required to reach that goal configuration from the starting configuration.
Input: 3 4 #BYY ..R# .BYR 4 #BYY ..R# .BYR #.YY ..R# BBYR #Y.Y B.R# .YRB #..R YYB# YBR. Output: 0 1 19 -1