Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 10319 Accepted Submission(s): 3736
Problem 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
Author
LL
在基础bfs上主要加上对钥匙的处理
题中的路是可以重复走的，但是状态是不一样的 比如说拿到某把钥匙了
用visit数组的话直接开3维
用1<<10 每一位上代表一个钥匙的状态
isupper 是判断 字符是否为大写字母 是就返回 1 不是返回0
islower 判断小写字母 返回值同上
#include <bits/stdc++.h> using namespace std; #define fi first #define se second #define pb push_back #define mset(a,b) memset(a,b,sizeof(a)) #define sz size() #define cl clear() #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 #define PI 3.1415926535897932384626433832795028841971693993751058209749445923078164 typedef long long ll; const int inf = 99999999; const double eps = 1e-8; const int dir4[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; const int dir8[8][2] = {{1,0},{-1,0},{0,1},{0,-1},{1,1},{1,-1},{-1,1},{-1,-1}}; struct node{ int x, y; int step; int state; node(){ } node(int x,int y,int step,int state) { this->x = x; this->y = y; this->step = step; this->state = state; } }; int n, m, T, sx, sy; int visit[21][21][1 << 10]; char mp[21][21]; int bfs() { queue<node> q; q.push(node(sx,sy,0,0)); //初始状态设置为0 即拿到 0把钥匙 每一位上为1时即对应拿到该位置的钥匙 visit[sx][sy][0] = 1; while(!q.empty()) { node t = q.front(); q.pop(); if(t.step >= T-1) break; //少走一部的情况下仍然没有到达终点并且大魔王巡视了 所以不可能到终点 for(int i = 0;i < 4;i ++) { int dx = t.x + dir4[i][0]; int dy = t.y + dir4[i][1]; int dt = t.step + 1; int ds = t.state; if(dx < 1 || dy < 1 || dx > n || dy > m || mp[dx][dy] == '*' || visit[dx][dy][ds]) continue; //如果遇到门 并且此时没有钥匙 if(isupper(mp[dx][dy]) && !(ds & (1 <<( mp[dx][dy] - 'A')))) continue; //到钥匙的位置 if(islower(mp[dx][dy])) { ds |= (1 << (mp[dx][dy] - 'a')); } if(mp[dx][dy] == '^') return dt; if(!visit[dx][dy][ds]) { visit[dx][dy][ds] = 1; q.push(node(dx,dy,dt,ds)); } } } return -1; } int main() { while(cin >> n >> m >> T) { mset(visit,0); for(int i = 1;i <= n;i ++) { for(int j = 1;j <= m;j ++) { cin >> mp[i][j]; if(mp[i][j] == '@') { sx = i; sy = j; } } } cout << bfs() << endl; } return 0; }
