Camelot#3063
Centuries ago, King Arthur and the Knights of the Round Table would gather on New Year's Day to celebrate their fellowship. In remembrance of these events, consider a solitaire board game in which a king and several knight pieces are placed at random on distinct squares of a chessboard.
The board is an 8 \times 8 array of squares (Figure 1).
Figure 1. Board
The king can move to any adjacent square, as shown in Figure 2, provided that the move does not leave the board.
Figure 2. All possible movements of the king
A knight can move as shown in Figure 3, as long as it remains on the board.
Figure 3. All possible movements of a knight
During the game, more than one piece can occupy the same square. The squares are considered large enough so there are no obstacles for the free movement of the pieces.
The player must move the king and knights so that all pieces gather in a single square in the minimum number of moves, following the movement rules described above. Additionally, whenever the king and one or more knights are in the same square, the player may move the king together with one of the knights as a single knight. Such a movement is counted as one move.
Write a program to determine the minimum number of moves required for the player to gather all pieces in a single square.
The input file contains a string describing the initial positions of the pieces on the board. The string contains a sequence of up to different board squares: the first corresponds to the king, and the rest to the knights (there are no more than knights). Each square is encoded by a letter-digit pair: the letter designates the horizontal coordinate, and the digit the vertical coordinate. All pieces start in different squares.
The output file must contain a single line with a positive integer indicating the minimum number of moves required to gather all pieces in one square.
Example 1