<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

536. Berland Chess
Time limit per test: 2 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Berland Chess is a single-player game played on a n x m rectangular chessboard. The chessboard has n rows, m columns, and is divided into n x 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.

Input
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.

Output
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.

Example(s)
sample input
sample output
7 9
.........
.........
.........
..R.K.R..
.........
.........
*........
9

<|response|>
## 1) Abridged problem statement (concise)

You are given an `n × m` board (`1 ≤ n,m ≤ 15`) with:
- `*` : one **white king** (moves 1 step in 8 directions),
- black pieces: `K` (knight), `B` (bishop), `R` (rook),
- `.` : empty.

Black pieces **never move**. The king must capture **all** black pieces.  
A king move is **illegal** if the destination square is attacked by **any black piece that is still alive**. Capturing removes that piece.

Output the **minimum number of king moves** to capture all pieces, or `-1` if impossible. If there are no black pieces, output `0`.

Constraint: total pieces (king + black) ≤ 15.

---

## 2) Key observations

1. **Only two things change** over time:
   - king position `(r,c)`
   - which black pieces have been captured

2. Because black pieces are static, we can model the game as a **shortest path problem** on a state graph.

3. Let there be `k` black pieces (`k ≤ 14`).  
   Use a bitmask `mask` of length `k`:
   - bit `i = 1` ⇒ piece `i` is captured/removed
   - bit `i = 0` ⇒ piece `i` is still alive

4. All moves have cost `1` ⇒ use **BFS** on states.

5. To validate a king move, we need to know whether a square is attacked by any **alive** black piece.  
   A common approach (and the one used in the given reference code) is:
   - Precompute, for each cell, which pieces attack it (`attack[r][c]` = set/list of piece indices),
   - During BFS, a cell is forbidden if it is attacked by some piece `i` with `mask` not containing `i`.

> Note: This precomputation uses the **initial** board as “blockers” for rook/bishop rays (stop at first non-empty cell). This matches the provided reference solution.

---

## 3) Full solution approach

### Step A — Parse the board
- Read `n, m` and the grid.
- Record:
  - king start cell `(sr, sc)`
  - list of black pieces `pieces[i] = (ri, ci)` and their type `ptype[i] ∈ {K,B,R}`

Let `k = number of black pieces`.

If `k == 0`, answer is `0`.

---

### Step B — Precompute attacked squares
Create `attack[r][c]` = collection of indices `i` such that piece `i` attacks cell `(r,c)`.

For each black piece `i`:
- If knight `K`: mark its 8 L-jumps.
- If bishop `B`: for each diagonal direction, walk until boundary or first non-`.` cell; mark all visited squares as attacked.
- If rook `R`: similarly for 4 orthogonal directions.

This gives fast “is square attacked by piece i?” queries.

---

### Step C — BFS on state space
State: `(r, c, mask)`  
- `(r,c)` = king position
- `mask` = which pieces are already captured

Start: `(sr, sc, 0)`  
Goal mask: `full = (1<<k) - 1`

Transitions:
- Try all 8 king moves to `(nr, nc)` inside board.
- Check safety:
  - if there exists `i in attack[nr][nc]` with `(mask & (1<<i)) == 0`, then square attacked by an alive piece ⇒ move illegal
- If `(nr, nc)` contains a black piece `i`, then capturing updates:
  - `nmask = mask | (1<<i)`
  - Otherwise `nmask = mask`

Run BFS storing `dist[r][c][mask]`.  
First time reaching any state with `mask == full` gives the minimum moves.

If BFS ends without reaching `full`, output `-1`.

---

### Complexity
- Board cells: ≤ 225
- Masks: ≤ 2^14 = 16384
- States: ≤ 225 * 16384 ≈ 3.7 million
- Each state explores up to 8 moves

Fits in time/memory in C++ and typically in Python with efficient structures.

---

## 4) C++ implementation (detailed comments)

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Berland Chess (p536)
  BFS over states: (king_r, king_c, captured_mask).

  Precompute attack[r][c] = indices of black pieces that attack (r,c)
  (using initial board as blockers for bishops/rooks), then in BFS we forbid
  moving into squares attacked by any *alive* piece (bit not set in mask).
*/

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    vector<string> board(n);
    for (int i = 0; i < n; i++) cin >> board[i];

    // Collect king position and black pieces
    int sr = -1, sc = -1;
    vector<pair<int,int>> pieces; // positions of black pieces
    vector<char> ptype;           // 'K', 'B', 'R' for each black piece

    for (int r = 0; r < n; r++) {
        for (int c = 0; c < m; c++) {
            char ch = board[r][c];
            if (ch == '*') {
                sr = r; sc = c;
            } else if (ch == 'K' || ch == 'B' || ch == 'R') {
                pieces.push_back({r, c});
                ptype.push_back(ch);
            }
        }
    }

    int k = (int)pieces.size();
    if (k == 0) {
        cout << 0 << "\n";
        return 0;
    }

    // attack[r][c] = set of indices of pieces that attack (r,c)
    vector<vector<vector<int>>> attack(n, vector<vector<int>>(m));

    // Precompute attacks for each piece i
    for (int idx = 0; idx < k; idx++) {
        auto [pr, pc] = pieces[idx];
        char typ = ptype[idx];

        if (typ == 'K') {
            // Black knight attacks in L shapes (±2,±1), (±1,±2)
            for (int dr = -2; dr <= 2; dr++) {
                for (int dc = -2; dc <= 2; dc++) {
                    if (abs(dr) + abs(dc) == 3) {
                        int nr = pr + dr, nc = pc + dc;
                        if (0 <= nr && nr < n && 0 <= nc && nc < m)
                            attack[nr][nc].push_back(idx);
                    }
                }
            }
        } else if (typ == 'B') {
            // Bishop: 4 diagonal rays until blocked by first non-empty cell
            const int dirs[4][2] = {{1,1},{1,-1},{-1,1},{-1,-1}};
            for (auto &d : dirs) {
                int dr = d[0], dc = d[1];
                for (int step = 1;; step++) {
                    int nr = pr + dr * step, nc = pc + dc * step;
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) break;
                    attack[nr][nc].push_back(idx);
                    if (board[nr][nc] != '.') break; // blocked further
                }
            }
        } else { // 'R'
            // Rook: 4 orthogonal rays until blocked by first non-empty cell
            const int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
            for (auto &d : dirs) {
                int dr = d[0], dc = d[1];
                for (int step = 1;; step++) {
                    int nr = pr + dr * step, nc = pc + dc * step;
                    if (nr < 0 || nr >= n || nc < 0 || nc >= m) break;
                    attack[nr][nc].push_back(idx);
                    if (board[nr][nc] != '.') break; // blocked further
                }
            }
        }
    }

    // Map a piece position to its index for O(1) capture-bit updates
    unordered_map<long long, int> pos_to_idx;
    pos_to_idx.reserve(k * 2);
    auto key = [&](int r, int c) -> long long { return 1LL * r * 100 + c; };
    for (int i = 0; i < k; i++) {
        pos_to_idx[key(pieces[i].first, pieces[i].second)] = i;
    }

    int full = (1 << k) - 1;

    // dist[r][c][mask] = minimum moves to reach state, -1 = unvisited
    vector<vector<vector<int>>> dist(
        n, vector<vector<int>>(m, vector<int>(1 << k, -1))
    );

    queue<array<int,3>> q;
    dist[sr][sc][0] = 0;
    q.push({sr, sc, 0});

    // 8 king moves
    const int KR[8] = {-1,-1,-1, 0,0, 1,1,1};
    const int KC[8] = {-1, 0, 1,-1,1,-1,0,1};

    while (!q.empty()) {
        auto [r, c, mask] = q.front();
        q.pop();

        int curd = dist[r][c][mask];
        if (mask == full) {
            cout << curd << "\n";
            return 0;
        }

        for (int d = 0; d < 8; d++) {
            int nr = r + KR[d], nc = c + KC[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m) continue;

            // Check if (nr,nc) is attacked by any alive piece
            bool bad = false;
            for (int idx : attack[nr][nc]) {
                if ((mask & (1 << idx)) == 0) { // idx is alive
                    bad = true;
                    break;
                }
            }
            if (bad) continue;

            // Capture if landing on a black piece square
            int nmask = mask;
            auto it = pos_to_idx.find(key(nr, nc));
            if (it != pos_to_idx.end()) {
                nmask |= (1 << it->second);
            }

            if (dist[nr][nc][nmask] == -1) {
                dist[nr][nc][nmask] = curd + 1;
                q.push({nr, nc, nmask});
            }
        }
    }

    cout << -1 << "\n";
    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
from collections import deque

def solve():
    n, m = map(int, input().split())
    board = [input().strip() for _ in range(n)]

    # Gather king and black pieces
    pieces = []   # (r,c)
    ptype = []    # 'K','B','R'
    sr = sc = -1
    for r in range(n):
        for c in range(m):
            ch = board[r][c]
            if ch == '*':
                sr, sc = r, c
            elif ch in "KBR":
                pieces.append((r, c))
                ptype.append(ch)

    k = len(pieces)
    if k == 0:
        print(0)
        return

    # attack[r][c] = list of piece indices that attack (r,c)
    attack = [[[] for _ in range(m)] for _ in range(n)]

    # Precompute attacks using the initial board as blockers for sliding pieces.
    for idx, ((pr, pc), typ) in enumerate(zip(pieces, ptype)):
        if typ == 'K':  # black knight
            for dr in range(-2, 3):
                for dc in range(-2, 3):
                    if abs(dr) + abs(dc) == 3:
                        nr, nc = pr + dr, pc + dc
                        if 0 <= nr < n and 0 <= nc < m:
                            attack[nr][nc].append(idx)

        elif typ == 'B':  # bishop
            for dr, dc in [(1,1),(1,-1),(-1,1),(-1,-1)]:
                step = 1
                while True:
                    nr, nc = pr + dr*step, pc + dc*step
                    if not (0 <= nr < n and 0 <= nc < m):
                        break
                    attack[nr][nc].append(idx)
                    if board[nr][nc] != '.':
                        break  # blocked
                    step += 1

        else:  # 'R' rook
            for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                step = 1
                while True:
                    nr, nc = pr + dr*step, pc + dc*step
                    if not (0 <= nr < n and 0 <= nc < m):
                        break
                    attack[nr][nc].append(idx)
                    if board[nr][nc] != '.':
                        break  # blocked
                    step += 1

    # Position -> piece index for O(1) capture checks
    pos_to_idx = {pos: i for i, pos in enumerate(pieces)}

    full = (1 << k) - 1

    # dist[r][c][mask] = minimum moves to reach state
    dist = [[[-1] * (1 << k) for _ in range(m)] for _ in range(n)]
    dist[sr][sc][0] = 0
    q = deque([(sr, sc, 0)])

    # 8 king moves
    KR = [-1,-1,-1, 0,0, 1,1,1]
    KC = [-1, 0, 1,-1,1,-1,0,1]

    while q:
        r, c, mask = q.popleft()
        curd = dist[r][c][mask]

        if mask == full:
            print(curd)
            return

        for d in range(8):
            nr, nc = r + KR[d], c + KC[d]
            if not (0 <= nr < n and 0 <= nc < m):
                continue

            # Check if (nr,nc) attacked by any alive piece
            unsafe = False
            for idx in attack[nr][nc]:
                if (mask & (1 << idx)) == 0:  # alive attacker
                    unsafe = True
                    break
            if unsafe:
                continue

            nmask = mask
            if (nr, nc) in pos_to_idx:
                nmask |= 1 << pos_to_idx[(nr, nc)]

            if dist[nr][nc][nmask] == -1:
                dist[nr][nc][nmask] = curd + 1
                q.append((nr, nc, nmask))

    print(-1)


if __name__ == "__main__":
    solve()
```

If you want, I can also provide a version that recomputes sliding-piece attacks dynamically after captures (more “physically accurate” for bishops/rooks), but the above matches the given reference approach.