题目链接：https://vjudge.net/contest/84620#problem/K
题目大意：一个人从起点走到终点，问他是否能够在规定的时间走到，在走向终点的路线上，可能会有一些障碍门，他需要在路上捡到开门的对应钥匙，才能通过这扇门。如果他到达终点的时间超过了规定时间，或者他根本就走不到终点，输出-1，否则的话，输出他走的步数。
解题思路：此题与普通的bfs类似，只不过到下一个点的时候，要加上一些判断，如果是钥匙，则将它储存起来，如果是门，则判断是否已经捡到了对应的钥匙，如果有对应钥匙，则这个门与其它 '.' 无异，如果没有对应的钥匙，则不能通过。这个功能是由状态压缩来实现的，将钥匙的对应序号转化成二进制，方便钥匙的存储和判断。另外，还有一个需要注意的就是vis数组的设置，此题只要仔细思考就会发现，设置成二维的显然不行，因为走过的路是可以重复走的，只不过你钥匙的数量要增加，比如说，你走到了一扇门那里，但是你没有钥匙，你只好向别的方向继续搜索，当你捡到对应的钥匙后，可以沿着原路返回到那扇门那里。因此，为了满足题目意思，又不需要走太多重复的路，这样的设置还是挺合理的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int vis[][][]; <<=
char map[][];
int dir[][] = {,,,,-,,,-};
int n, m,t; struct node
{
int x;
int y;
int key;
int step;
}; queue<node>q; int bfs()
{
node s,now, next;
int i, j,nx,ny;
while (!q.empty())
{
now = q.front();
q.pop();
if (map[now.x][now.y] == '^')
{
/*now.step < t ?printf("%d\n", now.step) : printf("-1\n"); */ //不能这样写，因为它可能走不到终点
if (now.step < t)return now.step;
}
for (i = ; i < ; i++)
{
nx = now.x + dir[i][];
ny = now.y + dir[i][];
if (nx < || nx >= n || ny < || ny >= m || map[nx][ny] == '*')continue;
else if ((map[nx][ny] == '.'||map[nx][ny]=='^') && !vis[nx][ny][now.key])
{
vis[nx][ny][now.key] = ;
next.x = nx, next.y = ny;
next.step = now.step + , next.key = now.key;
q.push(next);
}
else if (map[nx][ny] >= 'A'&&map[nx][ny] <= 'J'&&vis[nx][ny][now.key] == )
{
int key = << (map[nx][ny] - 'A');
if (now.key&key)
{
vis[nx][ny][now.key] = ;
next.x = nx, next.y = ny;
next.step = now.step + ;
next.key = now.key;
q.push(next);
}
}
else if (map[nx][ny] >= 'a'&&map[nx][ny] <= 'j' && !vis[nx][ny][now.key])
{
int key = << (map[nx][ny] -'a');
vis[nx][ny][now.key] = ;
next.x = nx, next.y = ny;
next.step = now.step + ;
next.key = now.key | key;
q.push(next);
}
}
}
return -;
} int main()
{
int i, j;
node s;
while (scanf("%d%d%d", &n, &m, &t) != EOF)
{
while (!q.empty())q.pop();
memset(vis, , sizeof(vis));
for (i = ; i < n; i++)
{
scanf("%s", &map[i]);
for (j = ; j < m; j++)
{
if (map[i][j] == '@')
{
s.x = i;
s.y = j;
map[i][j] = '.';
}
}
}
s.key = ; s.step = ;
vis[s.x][s.y][s.key] = ;
q.push(s);
printf("%d\n", bfs());
}
return ;
}
2018-03-26