p536.ans1
======================
9

=================
p536.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;
}

=================
p536.in1
======================
7 9
.........
.........
.........
..R.K.R..
.........
.........
*........

=================
statement.txt
======================
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

=================
