题意:给你一个三维地图,然后让你走出去,找到最短路径。

思路:bfs

  1. 每个坐标的表示为 x,y,z并且每个点都需要加上时间 t

    struct node
    {
    int x, y, z;
    int t;
    };

  2. bfs用队列,进队列的时候要标记,并且 t+1;
  3. 最先到达终点的,所花的时间必定最短

代码上的小技巧:
三维地图需要你去遍历的时候需要走六个方向:

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 ;
}

最新文章

  1. 自动显示隐藏布局的listView
  2. Laravel5.1-Eloquent ORM:起步
  3. XidianOJ 1177 Counting Stars
  4. 2016.5.27 PHP连接数据库与查询
  5. 由 argv引出的main参数 分类: C/C++ 2014-11-08 18:00 154人阅读 评论(0) 收藏
  6. VueJs一些资料网站链接
  7. linux ARP攻击处理
  8. Centos6.5源码编译安装nginx
  9. SQL(Oracle)日常使用与不常使用函数的汇总
  10. mac home/end/pageup/pageDown
  11. 【转】Tomcat源代码阅读系列
  12. arcgis api for js入门开发系列十五台风轨迹
  13. java File类常用方法
  14. C++智能指针及其简单实现
  15. Python - 安装并配置Anaconda环境
  16. 莫烦theano学习自修第一天【常量和矩阵的运算】
  17. Windows上Nginx的安装教程详解
  18. PHP 对 memcache操作类
  19. python安装whl文件的注意事项(windows系统)
  20. oracle相关命令收集-张

热门文章

  1. 教你如何在 IDEA 远程 Debug ElasticSearch
  2. spring cloud 测试的时候报 BeanCreationNotAllowedException: Error creating bean with name &#39;eurekaAutoServiceRegistration&#39; 但能正确跑完测试方法
  3. .net 中 Json 与List 相互转
  4. Eclipse - 安装语言包
  5. display:none和visibility:hidden v-show和v-if的区别
  6. 【持续更新】Java 时间相关
  7. Servlet之sendRedirect和getRequestDispatch
  8. SpringBoot热部署的两种方式
  9. 一键部署基于SVN开源版本控制系统
  10. 洛谷 P3119 [USACO15JAN]草鉴定Grass Cownoisseur