首页 > 代码库 > BNUOJ 5629 胜利大逃亡(续)
BNUOJ 5629 胜利大逃亡(续)
胜利大逃亡(续)
Time Limit: 2000ms
Memory Limit: 32768KB
This problem will be judged on HDU. Original ID: 142964-bit integer IO format: %I64d Java class name: Main
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训,把Ignatius关在一个n*m的地牢里,并在地牢的某些地方安装了带锁的门,钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置,离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次,若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试,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
每组测试数据之间有一个空行。
. 代表路
* 代表墙
@ 代表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暑期集训队练习赛(三)
解题:状态压缩搜索。。。。高级搜索?
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define INF 0x3f3f3f3f15 using namespace std;16 struct node{17 int state,step;18 node(int x = 0,int y = 0):state(x),step(y){}19 };20 char mp[30][30];21 int n,m,t,sx,sy,ex,ey;22 const int dir[4][2] = {0,-1,0,1,-1,0,1,0};23 queue<node>q;24 set<int>s;25 int compress(int x,int y,int state){26 int temp = x;27 temp = (temp<<5)|y;28 temp = (temp<<10)|state;29 return temp;30 }31 void decompress(int temp,int &x,int &y,int &state){32 int t = (1<<10)-1;33 state = temp&t;34 temp >>= 10;35 t = (1<<5)-1;36 y = temp&t;37 temp >>= 5;38 x = temp&t;39 }40 void addkey(int &state,int t){41 state |= (1<<t);42 }43 int haskey(int state,int t){44 return state&(1<<t);45 }46 int bfs(){47 while(!q.empty()) q.pop();48 s.clear();49 int i,j,x,y,tx,ty,tmpstate,tmp;50 tmp = compress(sx,sy,0);51 node temp2 = node(tmp,0);52 q.push(temp2);53 s.insert(tmp);54 while(!q.empty()){55 node temp2 = q.front();56 q.pop();57 if(temp2.step > t) return INF;//必须要的优化58 for(i = 0; i < 4; i++){59 decompress(temp2.state,x,y,tmpstate);60 if(x == ex && y == ey) return temp2.step;61 tx = x+dir[i][0];62 ty = y+dir[i][1];63 if(mp[tx][ty] == ‘*‘) continue;64 if(mp[tx][ty] >= ‘a‘ && mp[tx][ty] <= ‘j‘){65 addkey(tmpstate,mp[tx][ty]-‘a‘);66 }else if(mp[tx][ty] >= ‘A‘ && mp[tx][ty] <= ‘J‘){67 if(!haskey(tmpstate,mp[tx][ty]-‘A‘)) continue;68 }69 tmp = compress(tx,ty,tmpstate);70 if(s.count(tmp)) continue;71 s.insert(tmp);72 q.push(node(tmp,temp2.step+1));73 }74 }75 return INF;76 }77 int main(){78 while(~scanf("%d %d %d",&n,&m,&t)){79 memset(mp,‘*‘,sizeof(mp));80 getchar();81 for(int i = 1; i <= n; i++){82 for(int j = 1; j <= m; j++){83 mp[i][j] = getchar();84 if(mp[i][j] == ‘@‘) {sx = i;sy = j;}85 if(mp[i][j] == ‘^‘) {ex = i;ey = j;}86 }87 getchar();88 }89 int tmp = bfs();90 printf("%d\n",tmp < t?tmp:-1);91 }92 return 0;93 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。