好贷网好贷款

SDUT2193_救基友记3(BFS三维)

发布时间:2016-12-4 1:58:01 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SDUT2193_救基友记3(BFS三维)",主要涉及到SDUT2193_救基友记3(BFS三维)方面的内容,对于SDUT2193_救基友记3(BFS三维)感兴趣的同学可以参考一下。

救基友记3 Time Limit: 1000MS Memory limit: 65536K 题目描述   话说CZ由于不守基道,被妖怪抓走了,好基友WP在努力讨好高富帅RQ救出CZ的同时,CZ也意识到了自己的错误,然后努力的想逃出妖怪的闺房。     妖怪的闺房是一个n*m的矩阵,并且某些地方安装了带锁的门,钥匙藏在闺房另外的某些地方。刚开始WP被关在(sx,sy)的位置,离开闺房的门在(ex,ey)的位置。WP每分钟只能从一个坐标走到相邻四个坐标中的其中一个。妖怪每t分钟回闺房视察一次,若发现CZ不在原位置便把他再拎回去。经过若干次的尝试,CZ已画出整个闺房的地图。现在请你帮他计算能否再次成功逃亡。只要在妖怪下次视察之前走到出口就算离开闺房,如果妖怪回来的时候刚好走到出口或还未到出口都算逃亡失败。 输入  每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为闺房的地图,其中包括: . 代表路 * 代表墙 @ 代表CZ的起始位置 ^ 代表闺房的出口 A-J 代表带锁的门,对应的钥匙分别为a-j a-j 代表钥匙,对应的门分别为A-J 每组测试数据之间有一个空行。 输出  针对每组测试数据,如果可以成功逃亡,请输出最少需要多少分钟才能离开,如果不能则输出-1。 示例输入 4 5 17 @A.B. a*.*. *..*^ c..b* 4 5 16 @A.B. a*.*. *..*^ c..b* 示例输出 16 -1 解题报告 这是一题bfs的三维题。。。 把钥匙当成三维状态下的z轴,用二进制表示钥匙的有无,如0100100代表b和e的钥匙有。走到门的地方都要判断是否有该门的钥匙,有的话可以当作路走,没有的话当作墙。 走到钥匙的地方判断是否有该门的钥匙,有的话不要捡钥匙,没有的话捡起钥匙。 #include <iostream> #include <stdio.h> #include <string.h> #include <math.h> //#define using namespace std; struct node { int x,y,key,num; } q[1000000]; int n,m,t; char mmap[25][25]; int v[100][100][100]; int dx[]= {-1,0,1,0}; int dy[]= {0,1,0,-1}; int iskey(char c,int num) { int na,b; if(c>='A'&&c<='Z') na=c-'A'; else na=c-'a'; for(int i=0; i<=na; i++) { b=num%2; num/=2; } return b; } int bfs(int x,int y) { node now,next; now.x=x; now.y=y; now.num=0; now.key=0; int t=0,f=0; int i; q[f++]=now; v[now.x][now.y][now.key]=1; while(t<f) { now=q[t++]; //printf("x=%d,y=%d,num=%d,key=%d\n",now.x,now.y,now.num,now.key); if(mmap[now.x][now.y]=='^') { return now.num; } for(i=0; i<4; i++) { next.x=now.x+dx[i]; next.y=now.y+dy[i]; next.key=now.key; if(next.x>=0&&next.x<n&&next.y>=0&&next.y<m&&mmap[next.x][next.y]!='*'&&!v[next.x][next.y][next.key]) { if(mmap[next.x][next.y]>='a'&&mmap[next.x][next.y]<='j') { if(!iskey(mmap[next.x][next.y],next.key)) { next.key+=pow(2,mmap[next.x][next.y]-'a'); } next.num=now.num+1; q[f++]=next; v[next.x][next.y][next.key]=1; } else if(mmap[next.x][next.y]>='A'&&mmap[next.x][next.y]<='J') { if(iskey(mmap[next.x][next.y],next.key)) { next.num=now.num+1; q[f++]=next; v[next.x][next.y][next.key]=1; } } else { next.num=now.num+1; q[f++]=next; v[next.x][next.y][next.key]=1; } } } } return -1; } int main() { int i,j; while(scanf("%d%d%d",&n,&m,&t)!=EOF) { for(int i=0; i<n; i++) scanf("%s",mmap[i]); for(i=0; i<n; i++) { for(j=0; j<m; j++) { if(mmap[i][j]=='@') { break; } } if(j<m)break; } int ff=bfs(i,j); if(ff<t) printf("%d\n",ff); else printf("-1\n"); } }

上一篇:图像处理:基础(模板、卷积运算)
下一篇:Cocoa 框架 For iOS(一) 框架的介绍,Objectivie-C运行时能力的解析等

相关文章

相关评论