原题链接

题目大意

一个迷宫，相邻房间可能有门，可能有墙，可能直接连通。门的钥匙遍布在各个房间，对应的钥匙打开对应的门。问能否在规定时间之内逃出迷宫？

题目分析

求逃出迷宫最短时间，BFS. 这里存在的问题是：

怎么描述在房间拥有的钥匙的状态？

我们可以用一个整数的各个二进制位来表示是否拥有对应种类钥匙。和拯救大兵瑞恩一样的思路。

AC代码

#include <iostream> #include <queue> #include <cstring> using namespace std; const int maxn = 20 + 5; const int keyMax = 10 + 5; char maze[maxn][maxn]; bool vis[maxn][maxn][1 << keyMax]; int n, m, t; int sx, sy, ex, ey; int dir[4][2] = {1, 0, -1, 0, 0, 1, 0, -1}; struct node { int x, y; int t; int curKeys; }; int bfs() { queue<node> q; node s; s.x = sx, s.y = sy, s.t = 0, s.curKeys = 0; q.push(s); while(!q.empty()) { node cur = q.front(); q.pop(); if (cur.x == ex && cur.y == ey) return cur.t; for(int i = 0; i < 4; i++) { int cx = cur.x + dir[i][0]; int cy = cur.y + dir[i][1]; if (cx >= 1 && cx <= n && cy >= 1 && cy <= m) { if (maze[cx][cy] == '*') continue; if (maze[cx][cy] >= 'a' && maze[cx][cy] <= 'j') { node next; next.x = cx, next.y = cy; next.t = cur.t + 1; next.curKeys = cur.curKeys | (1 << (maze[cx][cy] - 'a' + 1)); if (vis[cx][cy][next.curKeys]) vis[cx][cy][next.curKeys] = false, q.push(next); } else if (maze[cx][cy] >= 'A' && maze[cx][cy] <= 'J'){ if ((cur.curKeys >> (maze[cx][cy] - 'A' + 1)) & 1) { node next; next.x = cx, next.y = cy; next.t = cur.t + 1; next.curKeys = cur.curKeys; if (vis[cx][cy][next.curKeys]) vis[cx][cy][next.curKeys] = false, q.push(next); } } else { node next; next.x = cx, next.y = cy; next.t = cur.t + 1; next.curKeys = cur.curKeys; if (vis[cx][cy][next.curKeys]) vis[cx][cy][next.curKeys] = false, q.push(next); } } } } return -1; } int main() { while(~(scanf("%d%d%d", &n, &m, &t))) { memset(maze, 0, sizeof(maze)); memset(vis, true, sizeof(vis)); getchar(); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { scanf("%c", &maze[i][j]); if (maze[i][j] == '@') {sx = i; sy = j;} if (maze[i][j] == '^') {ex = i; ey = j;} } getchar(); } int ans = bfs(); ans < t ? cout << ans : cout << -1; cout << endl; } }