400357: GYM100151 E Berland Chess

Berland Chess is a single-player game played on a n × m rectangular chessboard. The chessboard has n rows, m columns, and is divided into n × m squares.

There are two colors of pieces that can be present on the chessboard — white and black. You play as White. According to the rules, the chessboard always has the only white piece — the white king, the only piece you have in your possession. All black pieces standing on the chessboard belong to your opponent, a computer-controlled chess robot running "Chess Bermaster" software. There are four kinds of chess pieces:

• "*" — white king,
• "K" — black knight,
• "B" — black bishop,
• "R" — black rook.

No other pieces are allowed. Each chess piece has its own method of movement. Moves are made to vacant squares except when capturing an opponent's piece. Here are the rules of a single move, described for each chess piece:

• white king moves exactly one square horizontally, vertically, or diagonally;
• black knight moves two squares horizontally then one square vertically, or one square horizontally then two squares vertically;
• black bishop moves any number of vacant squares in any diagonal direction;
• black rook moves any number of vacant squares vertically or horizontally.

With the exception of any movement of the knight, pieces cannot jump over each other. Moves of a knight are not blocked by other pieces as it just jumps to the new location.

The goal of the game is to capture all opponent's black pieces by the white king. Fortunately for you, "Chess Bermaster" is stuck in the infinite loop today due to a bug in software, so black pieces will not be moving during the game at all.

You may never move white king into a position where he could be captured by one of the black pieces. When you capture a black piece yourself, the corresponding black piece gets removed from the chessboard and the white king replaces it on its square.

Find the minimum number of moves it will take the white king to capture all the black pieces.

The first line of input contains two integer numbers n, m (1 ≤ n, m ≤ 15) — the number of rows and columns on the chessboard, correspondingly. The next n lines contain m characters each — configuration of the chessboard. Each character will be one of the following:

• "." — an empty space,
• "*" — white king,
• "K" — black knight,
• "B" — black bishop,
• "R" — black rook.

There will be exactly one white king on the chessboard, and it will not be under attack in its initial position. The total number of pieces on the chessboard will never exceed 15. There are no restrictions on number of black pieces by specific kinds. For example, it is allowed that the chessboard contains three or more black knights.

Print a single integer — the minimum number of moves it will take the white king to capture all black pieces. If there are no black pieces on the chessboard, output 0. If it's impossible to capture all black pieces, output the only integer -1.

7 9
.........
.........
.........
..R.K.R..
.........
.........
*........

9