poj 2251 三维地图最短路径问题 bfs算法
2024-08-21 08:37:27
题意:给你一个三维地图,然后让你走出去,找到最短路径。
思路:bfs
- 每个坐标的表示为 x,y,z并且每个点都需要加上时间 t
struct node
{
int x, y, z;
int t;
}; - bfs用队列,进队列的时候要标记,并且 t+1;
- 最先到达终点的,所花的时间必定最短
代码上的小技巧:
三维地图需要你去遍历的时候需要走六个方向:
int dx[] = { ,,,,,- };
int dy[] = { ,,-,,, };
int dz[] = { ,-,,,, };
解决问题的代码:
#include <cstdio>
#include <iostream>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
int r, n, m;
string s[][];
struct node
{
int x, y, z;
int t;
};
node Begin, End;
queue <node> que;
int dx[] = { ,,,,,- };
int dy[] = { ,,-,,, };
int dz[] = { ,-,,,, };
int vis[][][];
int bfs()
{
que.push(Begin);
vis[Begin.x][Begin.y][Begin.z] = ;
while (!que.empty())
{
node front = que.front();
que.pop();
if (front.x == End.x && front.y == End.y && front.z == End.z) return front.t;
for (int i = ; i < ; i++)
{
node tmp;
tmp.x = front.x + dx[i];
tmp.y = front.y + dy[i];
tmp.z = front.z + dz[i];
tmp.t = front.t + ;
if (tmp.x >= && tmp.x < r && tmp.y >= && tmp.y < n && tmp.z >= && tmp.z < m && !vis[tmp.x][tmp.y][tmp.z] && s[tmp.x][tmp.y][tmp.z] != '#')
{
que.push(tmp);
vis[tmp.x][tmp.y][tmp.z] = ;
}
}
}
return -;
}
int main()
{
while (cin >> r >> n >> m)
{
if (r == && n == && m == ) break;
memset(vis, , sizeof(vis));
while (!que.empty())
{
que.pop();
}
for (int i = ; i < r; i++) {
string ret;
for (int j = ; j < n; j++) {
cin >> s[i][j];
for (int k = ; k < m; k++) {
if (s[i][j][k] == 'S') {
Begin.x = i, Begin.y = j, Begin.z = k; Begin.t = ;
}
else if (s[i][j][k] == 'E') {
End.x = i, End.y = j, End.z = k; End.t = ;
}
}
}
}
int ans = bfs();
if (ans == -) {
printf("Trapped!\n");
}
else {
printf("Escaped in %d minute(s).\n", ans);
}
} return ;
}
最新文章
- 自动显示隐藏布局的listView
- Laravel5.1-Eloquent ORM:起步
- XidianOJ 1177 Counting Stars
- 2016.5.27 PHP连接数据库与查询
- 由 argv引出的main参数 分类: C/C++ 2014-11-08 18:00 154人阅读 评论(0) 收藏
- VueJs一些资料网站链接
- linux ARP攻击处理
- Centos6.5源码编译安装nginx
- SQL(Oracle)日常使用与不常使用函数的汇总
- mac home/end/pageup/pageDown
- 【转】Tomcat源代码阅读系列
- arcgis api for js入门开发系列十五台风轨迹
- java File类常用方法
- C++智能指针及其简单实现
- Python - 安装并配置Anaconda环境
- 莫烦theano学习自修第一天【常量和矩阵的运算】
- Windows上Nginx的安装教程详解
- PHP 对 memcache操作类
- python安装whl文件的注意事项(windows系统)
- oracle相关命令收集-张
热门文章
- 教你如何在 IDEA 远程 Debug ElasticSearch
- spring cloud 测试的时候报 BeanCreationNotAllowedException: Error creating bean with name &#39;eurekaAutoServiceRegistration&#39; 但能正确跑完测试方法
- .net 中 Json 与List 相互转
- Eclipse - 安装语言包
- display:none和visibility:hidden v-show和v-if的区别
- 【持续更新】Java 时间相关
- Servlet之sendRedirect和getRequestDispatch
- SpringBoot热部署的两种方式
- 一键部署基于SVN开源版本控制系统
- 洛谷 P3119 [USACO15JAN]草鉴定Grass Cownoisseur