POJ2251 Dungeon Master 【BFS】

2023-10-06 19:01
文章标签 bfs master poj2251 dungeon

本文主要是介绍POJ2251 Dungeon Master 【BFS】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:http://poj.org/problem?id=2251
题意:给你一个三维迷宫,S是起点,E是终点,#不可走
解析:直接开个三维数组,BFS就好

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int inf = 0x7fffffff;
int L,R,C;
int vis[50][50][50];
char mapple[50][50][50];
int ans;
int dx[] = {0,1,-1,0,0,0};
int dy[] = {1,0,0,-1,0,0};
int dz[] = {0,0,0,0,1,-1};
int sx,sy,sz;
struct node
{int x,y,z;int step;node() {}node(int _x,int _y,int _z,int _step){x = _x;y = _y;z = _z;step = _step;}
};
int bfs()
{ans = inf;memset(vis,0,sizeof(vis));queue<node> q;q.push(node(sx,sy,sz,0));vis[sx][sy][sz] = 1;while(!q.empty()){node now = q.front();q.pop();if(mapple[now.x][now.y][now.z]=='E')return now.step;for(int i=0;i<6;i++){int tx = now.x+dx[i];int ty = now.y+dy[i];int tz = now.z+dz[i];if(tx<0||tx>=L || ty<0||ty>=R || tz<0 || tz>=C)continue;if(mapple[tx][ty][tz]=='#' || vis[tx][ty][tz])continue;vis[tx][ty][tz] = 1;q.push(node(tx,ty,tz,now.step+1));}}return inf;
}
int main(void)
{while(~scanf("%d %d %d",&L,&R,&C)){if(L==0&&R==0&&C==0)break;for(int i=0;i<L;i++){for(int j=0;j<R;j++){scanf("%s",mapple[i][j]);for(int k=0;k<C;k++){if(mapple[i][j][k]=='S'){sx = i;sy = j;sz = k;}}}}ans = bfs();if(ans==inf)puts("Trapped!");elseprintf("Escaped in %d minute(s).\n",ans);}return 0;
}

这篇关于POJ2251 Dungeon Master 【BFS】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/153780

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

java线程深度解析(四)——并发模型(Master-Worker)

http://blog.csdn.net/daybreak1209/article/details/51372929 二、Master-worker ——分而治之      Master-worker常用的并行模式之一,核心思想是由两个进程协作工作,master负责接收和分配任务,worker负责处理任务,并把处理结果返回给Master进程,由Master进行汇总,返回给客

xss-labs-master通关教程

一.level1 先来进行一下代码审计 <?php ini_set("display_errors", 0);//关闭错误显示$str = $_GET["name"]; //接受URL来的get形式的name传参echo "<h2 align=center>欢迎用户".$str."</h2>";//在网页输出,并不是echo执行的,而是echo把HTML代码发送到浏览器,浏览器对发送的H

双头BFS

牛客月赛100 D题,过了80%数据,调了一下午。。。烦死了。。。 还是没调试出来,别人的代码用5维的距离的更新有滞后性,要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx

Dungeon Master -uva

一个简答的三维BFS遍历,我从中领悟到了惨痛的教训,关于栈的溢出!!! 不多说了。。郁闷 #include<stdio.h>#include<string.h>#include<stdlib.h>#define MAX_SIZE 50 + 10int Dung[MAX_SIZE][MAX_SIZE][MAX_SIZE];int time[MAX_SIZE][MAX_SIZE][M

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历,在uva上找了个题敲了出来,感觉还不错,最近敲代码挺有手感的,希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in

【CF】D. Arthur and Walls(BFS + 贪心)

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’,如果有的话这个*就需要变成‘.’,利用BFS进行遍历,入队的要求是这个点为. 一开始将所有的'.'全部加入队列,如果碰到一个'*'变成'.'就入队,判断的时候从4个方向就行判断 题目链接:http://codeforces.com/contest/525/problem/D #include<cstdio>#include<