Time Limit: 2000MS | Memory Limit: 32768KB | 64bit IO Format: %I64d & %I64u |
Description
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带锁的门,钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置,离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次,若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试,Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢,如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。
Input
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图,其中包括:
. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙,对应的门分别为A-J
每组测试数据之间有一个空行。
Output
针对每组测试数据,如果可以成功逃亡,请输出需要多少分钟才能离开,如果不能则输出-1。
Sample Input
4 5 17
@A.B.
a*.*.
*..*^
c..b*
4 5 16
@A.B.
a*.*.
*..*^
c..b*
Sample Output
16
-1
Source
ACM暑期集训队练习赛(三)
思路:BFS+状压。因为最多有10把钥匙,就用二进制的10位分别表示某把钥匙的有无。走到钥匙就捡起钥匙,走到门就判断是否有钥匙,如果有就可以走。
AC代码:
#include <cstdio> #include <queue> #include <cstring> using namespace std; int n, m, t; char map[25][25]; bool vis[25][25][1 << 10]; struct node { int x, y, step, state; }; node start; queue <node> q; const int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0}; void input() { for (int i = 0; i < n; i++) scanf("%s", map[i]); } bool check(int x, int y) { if (x < 0 || x >= n || y < 0 || y >= m || map[x][y] == '*') return 0; return 1; } void pre() { for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) if (map[i][j] == '@') { start.x = i, start.y = j; map[i][j] = '.'; } start.step = start.state = 0; while (!q.empty()) q.pop(); memset(vis, 0, sizeof(vis)); } void solve() { pre(); q.push(start); vis[start.x][start.y][0] = 1; while (!q.empty()) { node u = q.front(); q.pop(); if (u.step >= t) break; if (map[u.x][u.y] == '^') { printf("%d\n", u.step); return; } node next; for (int i = 0; i < 4; i++) { next.x = u.x + dx[i]; next.y = u.y + dy[i]; if (!check(next.x, next.y)) continue; next.state = u.state; if (map[next.x][next.y] >= 'a' && map[next.x][next.y] <= 'j') next.state |= (1 << (map[next.x][next.y] - 'a')); else if (map[next.x][next.y] >= 'A' && map[next.x][next.y] <= 'Z') if (!((u.state >> (map[next.x][next.y] - 'A')) & 1)) continue; if (vis[next.x][next.y][next.state]) continue; vis[next.x][next.y][next.state] = 1; next.step = u.step + 1; q.push(next); } } printf("-1\n"); } int main() { while (scanf("%d%d%d", &n, &m, &t) == 3) { input(); solve(); } return 0; }
1 条评论
导师 · 2016年2月25日 上午11:41
dianlujitao还在竞赛?