棋盘上白子只有一个国王 黑子给出
各子遵从国际象棋的走法
黑子不动，白子不能走进黑子的攻击范围以内
问白字能不能吃掉所有的黑子
直接搜索就好了，各子状态用二进制表示
不过每个子被吃之后攻击范围会改变
所以重点是预处理每种剩余棋子状态的攻击范围
比较麻烦，注意白子吃掉一颗子之后所在的位置也可能是危险位置
//#pragma comment(linker, "/STACK:102400000,102400000")
//HEAD
#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <map>
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
//LOOP
#define FF(i, a, b) for(int i = (a); i < (b); ++i)
#define FD(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FE(i, a, b) for(int i = (a); i <= (b); ++i)
#define FED(i, b, a) for(int i = (b); i>= (a); --i)
#define REP(i, N) for(int i = 0; i < (N); ++i)
#define CLR(A,value) memset(A,value,sizeof(A))
#define CPY(a, b) memcpy(a, b, sizeof(a))
//STL
#define PB push_back
//INPUT
#define RI(n) scanf("%d", &n)
#define RII(n, m) scanf("%d%d", &n, &m)
#define RIII(n, m, k) scanf("%d%d%d", &n, &m, &k)
#define RS(s) scanf("%s", s)
//OUTPUT
#define WI(n) printf("%d
", n)
#define WS(s) printf("%s
", s)
typedef long long LL;
typedef unsigned long long ULL;
typedef vector <int> VI;
const int INF = 100000000;
const double eps = 1e-10;
const int maxn = 16;
const LL MOD = 1e9 + 7;
const int k = 1, b = 2, r = 3; ////表示棋子种类
int n, m, sx, sy, cnt, all;
bool danger[maxn][maxn][1 << 15], vis[maxn][maxn][1 << 15];
int dirk[][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1},
{2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
int dir[][2] = {{-1, -1}, {-1, 1}, {1, 1}, {1, -1},
{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
struct node{
int x, y, type;
}pie[maxn];
struct state{
short int x, y, key;
int step;
state(int a, int b, int c, int d) : x(a), y(b), key(c), step(d){}
};
char mat[maxn][maxn];
int num[maxn][maxn];
int bfs()
{
int tot = all - 1;
CLR(vis, 0);
vis[sx][sy][0] = 1;
queue<state> Q;
state t(sx, sy, 0, 0);
Q.push(t);
while (!Q.empty())
{
t = Q.front(); Q.pop();
if (t.key == tot)
return t.step;
REP(i, 8)
{
int nx = t.x + dir[i][0], ny = t.y + dir[i][1], key = t.key;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (num[nx][ny] != -1) ///若这个位置是棋子
key |= (1 << num[nx][ny]);
if (danger[nx][ny][key]) continue; ///key要是更新后的状态
if (!vis[nx][ny][key])
{
vis[nx][ny][key] = 1;
state heh(nx, ny, key, t.step + 1);
Q.push(heh);
}
}
}
return -1;
}
void solve()
{
all = 1 << cnt;
CLR(danger, 0);
int x, y;
REP(i, cnt)
{
int s0 = 1 << i;
if (pie[i].type == k)
{
REP(j, 8)
{
x = pie[i].x + dirk[j][0], y = pie[i].y + dirk[j][1];
if (x < 0 || x >= n || y < 0 || y >= m) continue;
REP(s0, all)
if ((s0 & (1 << i)) == 0)
danger[x][y][s0] = 1;
}
}
else if (pie[i].type == b)
{
REP(j, 4)
{
int st = 1;
while (1)
{
x = pie[i].x + dir[j][0] * st, y = pie[i].y + dir[j][1] * st;
if (x < 0 || x >= n || y < 0 || y >= m) break;
REP(s0, all)
if ((s0 & (1 << i)) == 0)
danger[x][y][s0] = 1;
st++;
if (mat[x][y] != '.') break; ///这里注意，先是标记这个点，再结束
}
}
}
else if (pie[i].type == r)
{
FF(j, 4, 8)
{
int st = 1;
while (1)
{
x = pie[i].x + dir[j][0] * st, y = pie[i].y + dir[j][1] * st;
if (x < 0 || x >= n || y < 0 || y >= m) break;
REP(s0, all)
if ((s0 & (1 << i)) == 0)
danger[x][y][s0] = 1;
st++;
if (mat[x][y] != '.') break;
}
}
}
}
WI(bfs());
}
int main()
{
while (~RII(n, m))
{
cnt = 0;
CLR(num, -1);
REP(i, n)
{
RS(mat[i]);
REP(j, m)
{
if (mat[i][j] == '*') sx = i, sy = j, mat[i][j] = '.';
else if (mat[i][j] == 'K') num[i][j] = cnt, pie[cnt].x = i, pie[cnt].y = j, pie[cnt].type = k, cnt++;
else if (mat[i][j] == 'B') num[i][j] = cnt, pie[cnt].x = i, pie[cnt].y = j, pie[cnt].type = b, cnt++;
else if (mat[i][j] == 'R') num[i][j] = cnt, pie[cnt].x = i, pie[cnt].y = j, pie[cnt].type = r, cnt++;
}
}
solve();
}
}