【题意】：给出一个n*m的国际象棋棋盘 (1 ≤ n, m ≤ 15)，棋盘里面只有四种棋子。
* 白色的皇 可以向任意周围八格移动一格
R 黑色的车 可以横着或竖着移动任意格
K 黑色的马 移动“日”字
B 黑色的象 可以斜着走任意格
已知棋盘最多有15个棋子，有且只有一个白色的皇， 且黑棋在吃不到皇的情况下是不会移动的。
问，在不被吃的情况下，皇最少用多少步可以吃光所有的黑棋。
【题解】：考虑到最多只有15个棋子，可以进行状态压缩的bfs。这里有个trick就是，象和车可能会被其他棋子挡着而吃不到皇。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "queue"
5 using namespace std;
6 int r, c, sx, sy;
7 int cnt;
8 char maz[20][20];
9 int maze[20][20];
10 bool visit[20][20][40000];
11 int dir[][2] = {0, 1, 1, 0, -1, 0, 0, -1, 1, -1, -1, 1, 1, 1, -1, -1};
12 int kdir[][2] = {-2, -1, -2, 1, 2, 1, 2, -1, 1, 2, 1, -2, -1, 2, -1, -2};
13 int bdir[][2] = {1, -1, 1, 1, -1, -1, -1, 1};
14 int rdir[][2] = {0, 1, 1, 0, -1, 0, 0, -1};
15 struct Node {
16 int x, y, ti, mask;
17 Node(){}
18 Node(int _x, int _y, int _ti, int _mask) {
19 x = _x, y = _y, ti = _ti, mask = _mask;
20 }
21 };
22
23 struct Piece {
24 int x, y, type;
25 Piece(){}
26 Piece(int _x, int _y, int _type) {
27 x = _x, y = _y, type = _type;
28 }
29 }p[20];
30
31 bool check(int x, int y) {
32 if(x >= 1 && x <= r && y >= 1 && y <= c) return true;
33 return false;
34 }
35
36 bool IsEat(int x, int y, int mask) {
37 //Knight
38 for(int i = 0; i < 8; i++) {
39 int xx = x + kdir[i][0], yy = y + kdir[i][1];
40 int tmp = maze[xx][yy];
41 if(!check(xx, yy)) continue;
42 if(tmp >= 0 && !(mask & (1 << tmp)) && p[tmp].type == 0) return true;
43 }
44 //Bishop
45 for(int i = 0; i < 4; i++) {
46 int xx = x + bdir[i][0], yy = y + bdir[i][1];
47 int tmp = maze[xx][yy];
48 while(check(xx, yy)) {
49 if(tmp >= 0 && !(mask & (1 << tmp))) {
50 if(p[tmp].type == 1) return true;
51 else break;
52 } else xx += bdir[i][0], yy += bdir[i][1], tmp = maze[xx][yy];
53 }
54 }
55 //Rook
56 for(int i = 0; i < 4; i++) {
57 int xx = x + rdir[i][0], yy = y + rdir[i][1];
58 int tmp = maze[xx][yy];
59 while(check(xx, yy)) {
60 if(tmp >= 0 && !(mask & (1 << tmp))) {
61 if(p[tmp].type == 2) return true;
62 else break;
63 } else xx += rdir[i][0], yy += rdir[i][1], tmp = maze[xx][yy];
64 }
65 }
66 return false;
67 }
68
69 int bfs() {
70 queue<Node> que;
71 memset(visit, false, sizeof(visit));
72 visit[sx][sy][0] = true;
73 que.push(Node(sx, sy, 0, 0));
74 while(!que.empty()) {
75 Node now = que.front();
76 que.pop();
77 if(now.mask == (1 << cnt) - 1) return now.ti;
78 for(int i = 0; i < 8; i++) {
79 int nx = now.x + dir[i][0], ny = now.y + dir[i][1], mask = now.mask;
80 if(!check(nx, ny)) continue;
81 int tmp = maze[nx][ny];
82 if(tmp >= 0) mask |= (1 << tmp);
83 if(visit[nx][ny][mask]) continue;
84 if(IsEat(nx, ny, mask)) continue;
85 que.push(Node(nx, ny, now.ti + 1, mask));
86 visit[nx][ny][mask] = true;
87 }
88 }
89 return -1;
90 }
91
92 int main() {
93 while(~scanf("%d%d", &r, &c)) {
94 cnt = 0;
95 memset(maze, -1, sizeof(maze));
96 for(int i = 1; i <= r; i++) scanf("%s", &maz[i][1]);
97 for(int i = 1; i <= r; i++) {
98 for(int j = 1; j <= c; j++) {
99 if(maz[i][j] == '.') continue;
100 if(maz[i][j] == '*') sx = i, sy = j;
101 else if(maz[i][j] == 'K') {
102 maze[i][j] = cnt, p[cnt++] = Piece(i, j, 0);
103 } else if(maz[i][j] == 'B') {
104 maze[i][j] = cnt, p[cnt++] = Piece(i, j, 1);
105 } else maze[i][j] = cnt, p[cnt++] = Piece(i, j, 2);
106 }
107 }
108 int ans = bfs();
109 cout << ans << endl;
110 }
111 return 0;
112 }