题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1429
思路分析：题目要求找出最短的逃亡路径，但是与一般的问题不同，该问题增加了门与钥匙约束条件；
考虑一般的搜索问题的解答思路：
搜索算法即在解空间中搜索满足要求的答案，可以看做一棵不断生长的状态树，状态之间不断扩展出新的状态，直到找出所需要的状态，即答案；
<1>定义状态：对于该问题，由于存在门与锁的约束条件，所以状态应该包括3个元素，即人所在的坐标 x 和 y 以及含有锁的种类；
<2>剪枝方法：因为在bfs搜索中会出现相同的状态，所以需要判重，使用vis数组即可；另外需要根据下一状态的位置已经该位置的字符判断能否拓展；
<3>状态压缩：对于拥有的钥匙进行状态压缩，使用一个10个位进行标记是否拥有钥匙 A~J ，将该10个bit压缩为一个整数即为状态压缩；
<4>位运算获得锁X与判断是否拥有锁X： 对于获得锁，可以使用或运算使第i个位为1,；判断是否拥有锁，可以使用与运算判断；
代码如下：
#include <queue>
#include <iostream>
using namespace std; #define MAX_N 21
#define KEY_N (1 << 10)
bool vis[MAX_N][MAX_N][KEY_N];
char map[MAX_N][MAX_N];
int dir[][] = {, -, , , -, , , };
int map_x, map_y; struct State
{
int x, y;
int step, key_value;
State() {}
State(int i, int j, int s, int k){ x = i; y = j; step = s; key_value = k; }
}; int GetKey(int key, char ch) { return key | ( << (ch - 'a')); }
bool OpenDoor(int key, char ch) { return key & ( << (ch - 'A')); } int Bfs(int x, int y, int game_times)
{
queue<State> state_queue;
State start(x, y, , ); vis[x][y][] = true;
state_queue.push(start);
while (!state_queue.empty())
{
State now = state_queue.front();
State next;
state_queue.pop(); if (now.step + >= game_times)
continue;
for (int i = ; i < ; ++i)
{
int n_x, n_y, n_step, n_key_value; n_x = now.x + dir[i][];
n_y = now.y + dir[i][];
n_step = now.step + ;
n_key_value = now.key_value;
if (n_x < || n_x >= map_x || n_y < || n_y >= map_y)
continue;
if (vis[n_x][n_y][n_key_value] || map[n_x][n_y] == '*')
continue;
if (map[n_x][n_y] == '^')
return n_step;
if ('a' <= map[n_x][n_y] && map[n_x][n_y] <= 'z')
{
n_key_value = GetKey(n_key_value, map[n_x][n_y]);
if (vis[n_x][n_y][n_key_value])
continue;
}
if ('A' <= map[n_x][n_y] && map[n_x][n_y] <= 'Z')
{
if (!OpenDoor(n_key_value, map[n_x][n_y]))
continue;
}
next.x = n_x;
next.y = n_y;
next.step = n_step;
next.key_value = n_key_value;
state_queue.push(next);
vis[n_x][n_y][n_key_value] = true;
}
}
return -;
} int main()
{
int game_times;
int start_x, start_y; while (scanf("%d %d %d\n", &map_x, &map_y, &game_times) != EOF)
{
int ans = ; memset(map, , sizeof(map));
memset(vis, , sizeof(vis));
for (int i = ; i < map_x; ++i)
{
scanf("%s", &map[i]);
for (int j = ; j < map_y; ++j)
{
if (map[i][j] == '@')
start_x = i, start_y = j;
}
} ans = Bfs(start_x, start_y, game_times);
if (ans == -)
printf("-1\n");
else
printf("%d\n", ans);
}
return ;
}