POJ2251 基础bfs

题目:

你进入了一个3D的宝藏地宫中探寻宝藏到了宝藏,你可以找到走出地宫的路带出宝藏,或者使用炉石空手回家。

地宫由立方体单位构成,立方体中不定会充满岩石。向上下前后左右移动一个单位需要一分钟。你不能对角线移动并且地宫四周坚石环绕。
请问你是否可以走出地宫带出宝藏?如果存在,则需要多少时间?

输入要求:

每个地宫描述的第一行为L,R和C(皆不超过30)。
L表示地宫的层数。
R和C分别表示每层地宫的行与列的大小。
随后L层地宫,每层R行,每行C个字符。
每个字符表示地宫的一个单元。'#'表示岩石单元,'.'表示空白单元。你的起始位置在'S',出口为'E'。
每层地宫后都有一个空行。L,R和C均为0时输入结束。

输出条件:

每个地宫对应一行输出。
如果可以带出宝藏,则输出
Escaped in x minute(s).
x为最短脱离时间。
如果无法带出,则输出
Trapped!

样例:

输入:

3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0
输出:
Escaped in 11 minute(s).
Trapped!

题目分析:考察bfs广度优先搜索算法,首先将起点入队,接着每一次遍历上下左右前后六个方向,如果可以通行就将该位置标记然后刷新到该坐标的步数,由于使用bfs具有最短路的性质,所以第一次到终点所用时间一定是最短时间。

代码:

#include <iostream>
#include<queue>

using namespace std;

struct pp
{
int x;
int y;
int z;
};//定义数据结构pp,用于储存三维坐标

queue<pp> s;//创建队列
pp ne, st;//st为起点的坐标,ne为每次朝六个方向探索时的可行坐标
int x, y, z,ans;//xyz为输入的内容,ans记录答案。
const int N = 35;
char a[N][N][N];
int d[N][N][N];//存储到达每个位置所需要的最短步数
int dx[6] = { -1,0,0,1,0,0 }, dy[6] = { 0,-1,0,0,1,0 }, dz[6] = { 0,0,-1,0,0,1 };//上下左右前后六个坐标的延伸

int bfs()
{
ans = -1;
memset(d, -1, sizeof d);//将d数组数据全部设置为-1
for (int i = 0; i < z; i++)
for (int j = 0; j < y; j++)
for (int k = 0; k < x; k++)
{
if (a[k][j][i] == 'S')
{
st.x = k, st.y = j, st.z = i;
d[k][j][i] = 0;
s.push(st);
break;
}
}//寻找起点S的位置,然后将起点坐标入队列,该点所在的d设为0
while (s.size())
{
pp temp = s.front();//取出队首元素
s.pop();//弹出队首元素
if (a[temp.x][temp.y][temp.z] == 'E')
{
ans= d[temp.x][temp.y][temp.z];
while (s.size()) s. pop();
break;
}//如果找到终点,终止循环
for (int i = 0; i < 6; i++)
{
int x1 = temp.x + dx[i];
int y1= temp.y + dy[i];
int z1 = temp.z + dz[i];
if (x1 < 0 || x1 >= x || y1 < 0 || y1 >= y || z1 < 0 || z1 >= z || d[x1][y1][z1] != -1 || a[x1][y1][z1] == '#') continue;
if(a[x1][y1][z1]=='.'||a[x1][y1][z1]=='E')
{
ne.x = x1, ne.y = y1, ne.z = z1;
d[x1][y1][z1] = d[temp.x][temp.y][temp.z] + 1;
s.push(ne);
}
}
}//每次朝六个方向延伸,如果该坐标可行则将该点坐标入队列,然后刷线该点所在的d数组的值。
return ans;
}

int main()
{
cin.tie(0);
while (cin>>z>>y>>x&&(x!=0||y!=0||z!=0))
{
for (int i = 0; i < z; i++)
for (int j = 0; j < y; j++)
for (int k = 0; k < x; k++)
cin >> a[k][j][i];
if (bfs() != -1) cout << "Escaped in " << bfs() << " minute(s)." << endl;
else cout << "Trapped!" << endl;

}

}

 

推荐这些文章:

29js基础,循环

<head> <meta charset="UTF-8"> <title>8循环结构</title></head><body> <script> //1,while循环 //2,do-while循环 //1,for循环 for (var i = 0; i <100 ; i++) { document.writeln(i+1+"<br>") } </script>&l...

【基础算法】差分

一维差分
差分可以看成前缀和的逆运算
构造差分数组b[]的方法:

作用:可以在\(O(1)\)的时间给区间[l, r]内的数都加上一个数c
模板题:AcWing 797. 差分
#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int a[N], b[N];

void insert(int l, int r, int c)
{
b[l] += c;
b[r + 1] -= c;
}

int main()
{
scanf("%d%d", &...

第十三届蓝桥杯大赛软件赛省赛C/C++大学B组真题(先占个位子有时间补)

A

B
C
D
E
F
G
H

(虽然贴代码也挺好但就是想试试新装的插件)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
const int N = 5e4 + 10;
int h[N], e[N], ne[N], idx;
int n, m, r;
bool st[N]; // 避免一个炸弹被多次引爆
struct Node
{
int x,...

蓝桥杯基础技能树题解一(1~5)

1001-地、颜色、魔法
解:
在n*m的矩形中有两种点','和'#',分别表示没用标记和有标记。被标记点完全包围的点(即从该点走到边界一定要经过至少一个标记点)同样视为被标记点。统计所有“标记点”的数量。
很基础的图遍历,用深度优先或者广度优先去遍历整张图都可以。由题意可以知道,一个点如果在矩阵的边界,那么它一定不是标记点。所以枚举每一个矩阵的边界点,若边界点是'.',则以该点为起点遍历整张图并在原图中染色。我们将可以走到的点重新标记为‘@’,则剩下来的‘#’和'.'就都是标记点了。最后用循环遍历整张图完成操作。
对于存图,由于1<=n,m<=1e6,所以直接开二维数组mp[m...

MATLAB基础语句(四)

第四部分:二维图像绘制
一、基本二维曲线的绘制
1、plot(y)
(1)y 是向量
  绘制以向量索引为横坐标,以向量元素值为纵坐标的图形

>> y1 = [1,5,11];
>> plot(y1)

三个对应坐标点(1,1)、(2,5)、(3,11)

(2)y 是实数矩阵
  绘制 y 的列向量对其坐标索引的图形

>> y2 = [1,3,8;2,5,10];
>> plot(y2)

共有3列坐标为
第一组:(1,1)、(1,2)
第一组:(2,3)、(2,5)
第一组:(3,8)、(3,10)

(3)y 是复数向量
plot( ...

《九日集训》第十五轮 (第八讲) 二级指针

知识点
二级指针
int **myMalloc(int r, int c, int* returnSize, int** returnColumnSizes) {
int i;
int **ret = (int **)malloc( sizeof(int *) * r ); // (1)
*returnColumnSizes = (int *)malloc( sizeof(int) * r ); // (2)
*returnSize = r; // (3)
f...

前缀和差分(一维和二维)

一维前缀和

例题

#include<iostream>
using namespace std;
const int N = 1e5+10;
int n,m;
int s[N],num[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++ )
{
cin >> num[i];
s[i] = s[i - 1] + num[i];
}
while(m -- )
{
int l,r...

LCP 37. 最小矩形面积

我们发现对于对答案有影响的点只能有斜率相邻的线能够产生,因此我们可以把斜率相同的放在一组,相邻计算即可。

class Solution {
public:
static bool cmp(pair<int,int> x,const pair<int,int> y){
if(x.first!=y.first)return x.first<y.first;
else return x.second<y.second;
}
double minRecSize(vector<vector<int...

【LeetCode】318. 最大单词长度乘积

class Solution {
public:
int maxProduct(vector<string>& words) {
int n = words.size();
int stat[n];
int wsize[n]; //存储单词长度
for(int i=0 ; i<n ; i++)
{
stat[i]=0;
wsize[i]=words[i].size();
for(int j=0;j<...

大连大学2022年4月程序设计竞赛-Raksasa的棋局

 
思路:多次查询的题应该打表

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
#include<cmath>
typedef long long ll;
using namespace std;
struct yuu{
int x,y,time;
};
queue<yuu> op;
int meme[1009][10...

文章标题:POJ2251 基础bfs
文章链接:https://www.dianjilingqu.com/50885.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇

)">
下一篇>>