题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1429 

题目大意

Ignatius被大魔王抓走,需要在t秒内逃出来,如果能逃出来输出最少耗时如果不能输出-1。Ignatius被关在一个n*m的迷宫内,小写字母代表钥匙,大写字母代表对应的门,Ignatius需要先拿到对应钥匙才能打开对应门,*代表墙,.代表空地,@代表Ignatius被大魔王关的位置,^代表出口。 

题解

BFS+状态压缩 压缩方式:用二进制表示是否拥有某钥匙

代码

/*
 * Author: Haipz
 * School: HDU
 * File Name: 1429.cpp
 */
#include <cstdio>
#include <cmath>
#include <ctime>
#include <cctype>
#include <cfloat>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

const int N = 2e1, M = 2e1, K = 1024;
const int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
char s[N + 5][M + 5];
struct node {
    int x, y, key;
    bool check(int n,int  m) {
        if (x >= 0 && y >= 0 && x < n && y < m) return true;
        return false;
    }
} h[N*M*K + 5];
int a[N + 5][M + 5][K + 5];
bool v[N + 5][N + 5][K + 5];

int main() {
    int n, m, t;
    while (scanf("%d%d%d%*c", &n, &m, &t) != EOF) {
        for (int i = 0; i < n; ++i) gets(s[i]);
        memset(a, -1, sizeof(a));
        memset(v, false, sizeof(v));
        int sx, sy, ex, ey;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < m; ++j) {
                if (s[i][j] == '@') sx = i, sy = j;
                if (s[i][j] == '^') ex = i, ey = j;
            }
        int head = 0, tail = 1;
        h[0].x = sx, h[0].y = sy, h[0].key = 0, a[sx][sy][0] = 0, v[sx][sy][0] = true;
        while (head < tail) {
            for (int i = 0; i < 4; ++i) {
                node t = h[head];
                t.x += dir[i][0], t.y += dir[i][1];
                if (!t.check(n, m)) continue;
                if (s[t.x][t.y] == '*') continue;
                if (islower(s[t.x][t.y])) t.key |= 1 << (s[t.x][t.y] - 'a');
                if (isupper(s[t.x][t.y]) && ((1 << (s[t.x][t.y] - 'A') & t.key) == 0)) continue;
                if (a[t.x][t.y][t.key] == -1 || a[h[head].x][h[head].y][h[head].key] + 1 < a[t.x][t.y][t.key]) {
                    a[t.x][t.y][t.key] = a[h[head].x][h[head].y][h[head].key] + 1;
                    if (!v[t.x][t.y][t.key]) h[tail++] = t, v[t.x][t.y][t.key] = true;
                }
            }
            ++head;
        }
        int ans = -1;
        for (int i = 0; i < K; ++i) ans = ans == -1 ? a[ex][ey][i] : min(ans, a[ex][ey][i] == -1 ? INT_MAX : a[ex][ey][i]);
        printf("%d\n", ans < t ? ans : -1);
    }
    return 0;
}

转载保留版权:http://haipz.com/blog/i/195 - 海胖博客