SP7969 ACPC10G - A Knights’ Tale

Imagine a chess board that extends indefinitely in both horizontal and vertical directions. N identical knights are placed on this board, each in a different square. N different squares are specially marked, which we will call the target squares, which could be different from where the knights are initially at. We would like you to determine the minimum number of knight-steps needed so that each of the target squares is occupied by one of the knights.  As illustrated in the figure, a knight moves using the normal ”L” move (1 square in one dimension and 2 squares in the other dimension.) For this problem, it is possible for more than one knight to occupy the same square while trying to reach its final destination as long as each knight ends up in a different target square.

Your program will be tested on one or more test cases. Each test case is specified using 2N +1 lines. The first line specifies (1 The last case is followed by a line with a single zero.

For each test case, print the following line: k. m Where k is the test case number (starting at one,) and m is the minimum number of moves.