题目链接：HDU1429

解题思路：正常搜最短路的图，但是走过的路可能重复走，因为可能拿到钥匙后沿路返回。要有一个记录口袋中钥匙相应状态的数组，由于有“a-j”10把钥匙，可以用10位二进制的数将其状态压缩到这个数中0表示没有，1表示有。可以加一个步数即使走最短路也到达不了终点的剪枝。注意记录行走状态的数组book要提前标记，不能等到pop了才标记，不然会爆内存…（PS:这题题目没说清楚被魔王抓回去钥匙会不会清空，不过根据答案来看显然是清空的，如果钥匙不清空的话可能还可以不走，等魔王抓回去，再利用回到原点的便捷节省步数，或者说被抓回去刷新走的步数，从而寻求到最短的方案，这样的话，每次行走还要把此时直接回到原点的情况入队）

AC代码：

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <vector>
#include <utility>
using namespace std;

/* 1，容易想到的一个剪枝是总的步数的最短不够t的check掉 2, 不能多搜到到达t秒那一层，不然空间会超过 */

struct node {
    int x,y;
    int step;
    int have;
};

char graph[21][21];
int n,m,t;
int sx,sy,ex,ey;
int nex[4][2] = {0,1,1,0,0,-1,-1,0};
int book[21][21][1<<10]; //状态记录

queue<node> Q;

bool judge (int x, int y) {
    if(x<1 || x>n || y<1 || y>m || graph[x][y] == '*')
        return false;
    return true;
}

bool check (int x, int y, int step) {
    if(abs(ex - x) + abs(ey - y) < t - step)
        return false;
    return true;
}

int BFS() {
    int i;
    node tmp, now;

    while(!Q.empty()) {
        Q.pop();
    }
    now.x = sx;
    now.y = sy;
    now.step = 0;
    now.have = 0;
    Q.push(now);
    memset(book,0,sizeof(book));
    book[now.x][now.y][now.have] = 1;

    while(!Q.empty()) {
        now = Q.front();
        Q.pop();
        if(now.step < t && now.x == ex && now.y == ey) {
            return now.step;
        }
        if(check(now.x,now.y,now.step)) {
            continue;
        }

        for (i = 0; i < 4; i++) {
            tmp.x = now.x + nex[i][0];
            tmp.y = now.y + nex[i][1];
            tmp.step = now.step + 1;
            tmp.have = now.have;

            if(judge(tmp.x, tmp.y)) {
                if(graph[tmp.x][tmp.y] == '.' && book[tmp.x][tmp.y][tmp.have] == 0) {
                    Q.push(tmp);
                    book[tmp.x][tmp.y][tmp.have] = 1;
                }else {
                    if(graph[tmp.x][tmp.y] >= 'a' && graph[tmp.x][tmp.y] <= 'j') {
                        tmp.have |= (1<<(graph[tmp.x][tmp.y] - 'a'));
                        if(book[tmp.x][tmp.y][tmp.have] == 0) {
                            Q.push(tmp);
                            book[tmp.x][tmp.y][tmp.have] = 1;
                        }
                    }else if(graph[tmp.x][tmp.y] >= 'A' && graph[tmp.x][tmp.y] <= 'J' && ((1<<(graph[tmp.x][tmp.y] - 'A')) & tmp.have) != 0) {
                        if(book[tmp.x][tmp.y][tmp.have] == 0) {
                            Q.push(tmp);
                            book[tmp.x][tmp.y][tmp.have] = 1;
                        }
                    }
            }
        }
    }
    return -1;
}

int main() {
    int i,j;

    while(~scanf("%d%d%d",&n,&m,&t)) {
        getchar();
        for (i = 1; i <= n; i++) {
            for (j = 1; j <= m; j++) {
                scanf("%c", &graph[i][j]);
                if(graph[i][j] == '@') {
                    sx = i;
                    sy = j;
                    graph[i][j] = '.';
                }else if(graph[i][j] == '^') {
                    ex = i;
                    ey = j;
                    graph[i][j] = '.';
                }
            }
            getchar();
        }
        /* for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { printf("%c",graph[i][j]); } printf("\n"); } printf("%d %d %d %d\n",sx,sy,ex,ey); */
        while(!Q.empty()) {
            Q.pop();
        }
        printf("%d\n",BFS());
    }
    return 0;
}