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

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;
vector<string> tbl;
vector<pair<int, int>> pieces;
vector<char> ptype;
int kpos;

void read() {
    cin >> n >> m;
    tbl.resize(n);
    cin >> tbl;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {
            if(tbl[i][j] == '*') {
                kpos = i * m + j;
            } else if(tbl[i][j] == 'K' || tbl[i][j] == 'B' || tbl[i][j] == 'R') {
                pieces.emplace_back(i, j);
                ptype.push_back(tbl[i][j]);
            }
        }
    }
}

void solve() {
    // We can solve this with a fairly simple BFS by extending the state. As
    // black pieces don't move, the state is fully defined by the position of
    // the king, and the state of figures that have been taken (which can be
    // kept as a 3-bit mask). Initially we will just cover the cells that are
    // blocked.

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

    vector<vector<set<int>>> attack(n, vector<set<int>>(m));
    for(int idx = 0; idx < k; idx++) {
        auto [ci, cj] = pieces[idx];
        char type = ptype[idx];
        if(type == 'K') {
            for(int di = -2; di <= 2; di++) {
                for(int dj = -2; dj <= 2; dj++) {
                    if(abs(di) + abs(dj) == 3) {
                        int ni = ci + di, nj = cj + dj;
                        if(ni >= 0 && ni < n && nj >= 0 && nj < m) {
                            attack[ni][nj].insert(idx);
                        }
                    }
                }
            }
        } else if(type == 'B') {
            for(int d = 0; d < 4; d++) {
                int di = (d == 0 || d == 1) ? 1 : -1;
                int dj = (d == 0 || d == 2) ? 1 : -1;
                for(int step = 1;; step++) {
                    int ni = ci + di * step, nj = cj + dj * step;
                    if(ni < 0 || ni >= n || nj < 0 || nj >= m) {
                        break;
                    }
                    attack[ni][nj].insert(idx);
                    if(tbl[ni][nj] != '.') {
                        break;
                    }
                }
            }
        } else if(type == 'R') {
            for(int d = 0; d < 4; d++) {
                int di = (d == 0) ? 1 : ((d == 1) ? -1 : 0);
                int dj = (d == 2) ? 1 : ((d == 3) ? -1 : 0);
                for(int step = 1;; step++) {
                    int ni = ci + di * step, nj = cj + dj * step;
                    if(ni < 0 || ni >= n || nj < 0 || nj >= m) {
                        break;
                    }
                    attack[ni][nj].insert(idx);
                    if(tbl[ni][nj] != '.') {
                        break;
                    }
                }
            }
        }
    }

    queue<array<int, 3>> q;
    vector<vector<vector<int>>> dist(
        n, vector<vector<int>>(m, vector<int>(1 << k, -1))
    );
    int start_mask = 0;
    dist[kpos / m][kpos % m][start_mask] = 0;
    q.push({kpos / m, kpos % m, start_mask});

    int dr[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    int dc[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

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

        if(mask == (1 << k) - 1) {
            cout << dist[ci][cj][mask] << "\n";
            return;
        }

        for(int d = 0; d < 8; d++) {
            int ni = ci + dr[d];
            int nj = cj + dc[d];
            if(ni < 0 || ni >= n || nj < 0 || nj >= m) {
                continue;
            }

            bool attacked = false;
            for(int idx: attack[ni][nj]) {
                if(!(mask & (1 << idx))) {
                    attacked = true;
                    break;
                }
            }
            if(attacked) {
                continue;
            }

            int nmask = mask;
            char cell = tbl[ni][nj];
            if(cell == 'K' || cell == 'B' || cell == 'R') {
                for(int idx = 0; idx < k; idx++) {
                    if(pieces[idx] == make_pair(ni, nj)) {
                        nmask |= (1 << idx);
                        break;
                    }
                }
            }

            if(dist[ni][nj][nmask] == -1) {
                dist[ni][nj][nmask] = dist[ci][cj][mask] + 1;
                q.push({ni, nj, nmask});
            }
        }
    }

    cout << -1 << "\n";
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 5) Python implementation (detailed comments)

```python
from collections import deque

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

    pieces = []   # list of (r,c) for each black piece
    ptype = []    # 'K','B','R' for each piece (black knight/bishop/rook)
    king_r = king_c = -1

    # Parse the board: find king and black pieces
    for i in range(n):
        for j in range(m):
            ch = tbl[i][j]
            if ch == '*':
                king_r, king_c = i, j
            elif ch in "KBR":
                pieces.append((i, j))
                ptype.append(ch)

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

    # attack[r][c] will store a list of indices of pieces that attack (r,c).
    attack = [[[] for _ in range(m)] for _ in range(n)]

    # Precompute all attacked squares for each black piece, based on initial board.
    for idx, ((ci, cj), typ) in enumerate(zip(pieces, ptype)):
        if typ == 'K':  # black knight
            for di in range(-2, 3):
                for dj in range(-2, 3):
                    if abs(di) + abs(dj) == 3:  # (2,1) / (1,2)
                        ni, nj = ci + di, cj + dj
                        if 0 <= ni < n and 0 <= nj < m:
                            attack[ni][nj].append(idx)

        elif typ == 'B':  # bishop: 4 diagonal rays
            dirs = [(1, 1), (1, -1), (-1, 1), (-1, -1)]
            for di, dj in dirs:
                step = 1
                while True:
                    ni, nj = ci + di * step, cj + dj * step
                    if not (0 <= ni < n and 0 <= nj < m):
                        break
                    attack[ni][nj].append(idx)
                    # Stop ray when hitting a non-empty square
                    if tbl[ni][nj] != '.':
                        break
                    step += 1

        else:  # 'R' rook: 4 orthogonal rays
            dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
            for di, dj in dirs:
                step = 1
                while True:
                    ni, nj = ci + di * step, cj + dj * step
                    if not (0 <= ni < n and 0 <= nj < m):
                        break
                    attack[ni][nj].append(idx)
                    if tbl[ni][nj] != '.':
                        break
                    step += 1

    # Map piece position -> index to quickly set capture bit
    pos_to_idx = {pos: i for i, pos in enumerate(pieces)}

    # dist[r][c][mask] = min moves, initialized to -1 (unvisited)
    dist = [[[-1] * (1 << k) for _ in range(m)] for _ in range(n)]

    start_mask = 0
    dist[king_r][king_c][start_mask] = 0
    q = deque([(king_r, king_c, start_mask)])

    # 8 king moves
    dr = [-1, -1, -1,  0, 0, 1, 1, 1]
    dc = [-1,  0,  1, -1, 1,-1, 0, 1]

    full = (1 << k) - 1

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

        if mask == full:
            print(curd)
            return

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

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

            nmask = mask
            # If we moved onto a black piece square, we capture it
            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()
```
