永夜初晗

  • 主页
  • 文章列表
  • 三国闯关杀
所有文章 友链 关于我

永夜初晗

  • 主页
  • 文章列表
  • 三国闯关杀

POJ2251 Dungeon Master 解题报告

9月 15

题目大意:这题是一个三维的迷宫题目,其中用·表示空地,#表示障碍物,S表示起点,E表示终点,求从起点到终点的最小移动次数,解法和二维的类似,只是在行动时除了东南西北移动外还多了上下。

对于题目给出数据的含义就是输入l,r,c,分别代表迷宫有l层,每层长宽分别是c,r。

对于数据一可以这样移动
(1,1,1)->(1,1,2)->(1,1,3)->(1,1,4)->(1,1,5)->(1,2,5)->(1,3,5)->(1,3,4)->(1,4,4)->(2,4,4)->(2,4,5)->(3,4,5)
共11步就可以到达终点

对于数据二明显不能到达,则输出Trapped

这题用BFS解,每次去队首元素,如果是终点则输出结果移动的次数,否则,从该点开始分别向东南西北上下移动(如果可以走的话)并继续搜,如果到队列为空还没搜到解法,则说明无解。

poj2251 Dungeon Masterview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std;
bool hash[35][35][35];
char map[35][35][35];
struct prog{
int x;int y;int z; //定义点的坐标
int step; //移动的步子数
};
int main()
{
int l , r , c ;
while ( cin >> l >> r >> c , l && r && c )
{
int i , j , k;
prog start;
memset(hash,false,sizeof(hash));//初始化为false,表示每条路都没走过
for ( i = 0 ; i < l ; i ++ )
{
for ( j = 0 ; j < r ; j ++ )
{
cin >> map [i][j];
for ( k = 0 ; k < c ; k ++ )
{
if(map[i][j][k]=='S')
{//对起点的相关变量初始化
start.x=i;
start.y=j;
start.z=k;
start.step=0;
hash[i][j][k]=true;
}
}
}
}

queue<prog>bfs;
bfs.push(start); //起点入队
bool found=false; //标记变量,判断是否找到最优解,如果为true则说明从起点到终点存在着解

while(!bfs.empty())
{
prog tmp=bfs.front();
bfs.pop();

if(map[tmp.x][tmp.y][tmp.z]=='E')
{//已经到了终点,则将标记变量设为true,并输出答案
found=true;
cout<<"Escaped in "<<tmp.step<<" minute(s)."<<endl;
break;
}

tmp.step++; //移动步子+1
prog tmp2;
if(tmp.x>0)
{//向下走,所以改点不能在第一层,则x要大于0
tmp2=tmp;
tmp2.x--;
if(map[tmp2.x][tmp2.y][tmp2.z]!='#'&&hash[tmp2.x][tmp2.y][tmp2.z]==false)
{//如果下一层不是障碍物并且也没走过,则往下走,并标记该点已走过,入队
hash[tmp2.x][tmp2.y][tmp2.z]=true;
bfs.push(tmp2);
}
}

//下面搜索方法同上 注释略
if(tmp.x<l-1)
{//向上
tmp2=tmp;
tmp2.x++;
if(map[tmp2.x][tmp2.y][tmp2.z]!='#'&&hash[tmp2.x][tmp2.y][tmp2.z]==false)
{
hash[tmp2.x][tmp2.y][tmp2.z]=true;
bfs.push(tmp2);
}
}

if(tmp.y>0)
{//向北
tmp2=tmp;
tmp2.y--;
if(map[tmp2.x][tmp2.y][tmp2.z]!='#'&&hash[tmp2.x][tmp2.y][tmp2.z]==false)
{
hash[tmp2.x][tmp2.y][tmp2.z]=true;
bfs.push(tmp2);
}
}

if(tmp.y<r-1)
{//向南
tmp2=tmp;
tmp2.y++;
if(map[tmp2.x][tmp2.y][tmp2.z]!='#'&&hash[tmp2.x][tmp2.y][tmp2.z]==false)
{
hash[tmp2.x][tmp2.y][tmp2.z]=true;
bfs.push(tmp2);
}
}

if(tmp.z>0)
{//向西
tmp2=tmp;
tmp2.z--;
if(map[tmp2.x][tmp2.y][tmp2.z]!='#'&&hash[tmp2.x][tmp2.y][tmp2.z]==false)
{
hash[tmp2.x][tmp2.y][tmp2.z]=true;
bfs.push(tmp2);
}
}

if(tmp.z<c-1)
{//向东
tmp2=tmp;
tmp2.z++;
if(map[tmp2.x][tmp2.y][tmp2.z]!='#'&&hash[tmp2.x][tmp2.y][tmp2.z]==false)
{
hash[tmp2.x][tmp2.y][tmp2.z]=true;
bfs.push(tmp2);
}
}

}
if(!found)//如果没有找到解
cout<<"Trapped!"<<endl;
}
return 0;
}
  • 数据结构
  • 广度优先搜索
  • poj
  • 搜索
  • 队列
  • 算法竞赛

扫一扫,分享到微信

微信分享二维码
POJ2689 Prime Distance 素数筛选
POJ 2253 Frogger 解题报告
© 2018 永夜初晗
Hexo Theme Yilia by Litten
  • 所有文章
  • 友链
  • 关于我

tag:

  • 算法竞赛入门经典训练指南
  • 动态规划
  • 排序
  • 计算几何
  • 贪心
  • 离散
  • 二分
  • 深度优先搜索
  • 递归
  • 状态压缩
  • codeforces
  • 最大公约数
  • 数论
  • 矩阵
  • 快速幂
  • 素性测试
  • 素数
  • burnside
  • polya
  • AC自动机
  • kmp
  • 字典树
  • 字符串匹配
  • 数据结构
  • 欧拉函数
  • 筛选
  • hdu
  • 并查集
  • 线段树
  • 仙剑
  • 感动
  • 语录
  • 背包问题
  • 优先队列
  • 枚举
  • 后缀数组
  • 旋转
  • 卡特兰数
  • 广度优先搜索
  • 最短路
  • 二分图
  • 图论
  • 最大匹配
  • 算法
  • poj
  • 中国剩余定理
  • 矩形
  • 分治
  • 规律
  • Linux
  • crontab
  • 同余方程
  • 扩展欧几里得
  • 记忆化搜索
  • floyd
  • prim
  • 生成树
  • 费马小定理
  • kruskal
  • 位运算
  • 高斯消元
  • 匈牙利算法
  • 最小覆盖点
  • 搜索
  • 最长公共子序列
  • DP
  • 队列
  • 排列
  • 组合数学
  • 最小生成树
  • 抽屉原理
  • 高精度
  • 欧几里得
  • 斐波那契数列
  • 法雷级数
  • usaco
  • 测试数据
  • 二叉树
  • 矩形切割
  • 阶乘
  • spfa
  • 背包
  • 欧拉回路
  • 康托展开
  • zoj
  • 反素数
  • 归并排序
  • 逆序对

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 《算法竞赛入门经典训练指南》动态规划习题1

    2018-09-16

    #算法竞赛入门经典训练指南#动态规划

  • 《算法竞赛入门经典训练指南》动态规划习题2

    2018-09-16

    #算法竞赛入门经典训练指南#动态规划

  • 《算法竞赛入门经典训练指南》高效算法设计举例1

    2018-09-16

    #算法竞赛入门经典训练指南#排序#计算几何#贪心

  • 《算法竞赛入门经典训练指南》高效算法设计举例2

    2018-09-16

    #算法竞赛入门经典训练指南#动态规划#离散#二分

  • 《算法竞赛入门经典训练指南》问题求解常见策略1

    2018-09-16

    #算法竞赛入门经典训练指南#深度优先搜索#递归

  • 《算法竞赛入门经典训练指南》问题求解常见策略2

    2018-09-16

    #算法竞赛入门经典训练指南#二分#深度优先搜索

  • 《算法竞赛入门经典训练指南》动态规划专题1

    2018-09-16

    #算法竞赛入门经典训练指南#动态规划#递归#状态压缩

  • 《算法竞赛入门经典训练指南》动态规划专题2

    2018-09-16

    #算法竞赛入门经典训练指南#动态规划#状态压缩

  • 《算法竞赛入门经典训练指南》思维的体操

    2018-09-16

    #算法竞赛入门经典训练指南#贪心#数论

  • 20111120周赛解题报告

    2018-09-16

    #最大公约数#数论

  • Codeforces Round #118 (Div. 2) :A. Comparing Strings

    2018-09-16

    #codeforces

  • Codeforces Round #118 (Div. 2) :B. Growing Mushrooms

    2018-09-16

    #codeforces

  • Codeforces Round #118 (Div. 2) :C. Plant

    2018-09-16

    #codeforces#矩阵#快速幂

  • Codeforces Round #118 (Div. 2) :D. Mushroom Scientists

    2018-09-16

    #codeforces#数论

  • AC自动机简单模版

    2018-09-16

    #AC自动机#kmp#字典树#字符串匹配#数据结构

  • 欧拉函数模板

    2018-09-16

    #素数#欧拉函数#筛选

  • 矩阵快速幂模板

    2018-09-16

    #矩阵#快速幂

  • burnside定理,polya计数 模版

    2018-09-16

    #burnside#polya

  • 素性测试 miller rabin+pollard rho

    2018-09-16

    #素性测试#素数

  • 潸然泪下 盘点仙剑十大让人动情女子

    2018-09-16

    #仙剑#感动

  • 仙剑四十大感人经典语录

    2018-09-16

    #仙剑#感动#语录

  • hdu1016 Prime Ring Problem解题报告

    2018-09-16

    #深度优先搜索#素数#hdu

  • hdu1232 畅通工程 解题报告

    2018-09-16

    #数据结构#hdu#并查集

  • hdu1247 Hat’s Words 解题报告

    2018-09-16

    #字典树#数据结构#hdu

  • hdu1604 Deque 2013多校第一场1005

    2018-09-16

    #动态规划#hdu

  • hdu1711 Number Sequence 解题报告

    2018-09-16

    #kmp#hdu

  • hdu1754 I Hate It 解题报告

    2018-09-16

    #数据结构#hdu#线段树

  • hdu1785 You Are All Excellent

    2018-09-16

    #数论#hdu

  • hdu1896 Stones 解题报告

    2018-09-16

    #hdu#优先队列

  • hdu2036和hdu2108 叉乘的运用

    2018-09-16

    #计算几何#hdu

  • hdu2222 Keywords Search 解题报告

    2018-09-16

    #AC自动机#kmp#数据结构#hdu

  • hdu2955 Robberies 教你怎样抢银行划算!

    2018-09-16

    #动态规划#hdu#背包问题

  • hdu2971 Tower 矩阵快速幂

    2018-09-16

    #递归#矩阵#快速幂#hdu

  • hdu4161 Iterated Difference 解题报告

    2018-09-16

    #hdu#枚举

  • hdu4162 Shape Number 解题报告

    2018-09-16

    #数据结构#hdu#枚举#后缀数组#旋转

  • hdu4163 Stock Prices 解题报告

    2018-09-16

    #排序#hdu

  • hdu4165 Pills 解题报告

    2018-09-16

    #递归#数论#hdu#卡特兰数

  • hdu4291 A Short problem 矩阵快速幂 成都区预赛的一题

    2018-09-16

    #矩阵#快速幂#hdu

  • hdu4300 Clairewd’s message 多校第一场

    2018-09-16

    #kmp#hdu

  • hdu4301 Divide Chocolate 动态规划解题报告(多校1)

    2018-09-16

    #动态规划#hdu

  • hdu4308 Saving Princess claire 搜索解题报告(多校1)

    2018-09-16

    #hdu#广度优先搜索#最短路

  • hdu4412 Sky Soldiers 动态规划 杭州网赛的第三题

    2018-09-16

    #动态规划#hdu

  • hdu4419 Colourful Rectangle 搜索+矩形分割 杭州赛区网赛最后一题

    2018-09-16

    #深度优先搜索#hdu#矩形#分治

  • hdu4602 Partition 2013多校第一场100

    2018-09-16

    #递归#数论#hdu

  • hdu4611 Balls Rearrangement 最大公约数 2013多校2-1001

    2018-09-16

    #最大公约数#数论#hdu

  • hdu4619 Warm up 2 二分图匹配 2013多校第二场1009

    2018-09-16

    #贪心#hdu#二分图#图论#最大匹配

  • hdu4632 Palindrome subsequence 20103多校4-1001

    2018-09-16

    #动态规划#hdu

  • [转]高级数据结构设计--并查集及实现学习笔记(有趣篇)

    2018-09-16

    #数据结构#并查集#算法

  • Linux命令之Crontab学习笔记

    2018-09-16

    #Linux#crontab

  • poj1006 中国剩余定理

    2018-09-16

    #数论#poj#中国剩余定理

  • POJ1019 ---简单的数学找规律题

    2018-09-16

    #递归#poj#规律

  • poj1050经典DP的二维形式

    2018-09-16

    #动态规划#poj

  • 通过POJ1061青蛙的约会来谈扩展欧几里得算法

    2018-09-16

    #数论#poj#同余方程#扩展欧几里得

  • POJ 1062 昂贵的聘礼 解题报告

    2018-09-16

    #最短路#图论#poj

  • poj1080 人类基因配对

    2018-09-16

    #动态规划#poj

  • poj1088记忆化搜索

    2018-09-16

    #poj#记忆化搜索

  • POJ 1125 Stockbroker Grapevine 解题报告

    2018-09-16

    #最短路#图论#poj#floyd

  • poj1141 Brackets Sequence(经典DP) 解题报告另附官方测试数据

    2018-09-16

    #动态规划#字符串匹配#poj

  • POJ1142Smith Numbers一道简单的数学题

    2018-09-16

    #数论#poj

  • poj1191棋盘分割(动态规划)

    2018-09-16

    #动态规划#poj

  • POJ1222EXTENDED LIGHTS OUT 解题报告

    2018-09-16

    #枚举#poj#位运算#高斯消元

  • POJ1251 Jungle Roads 解题报告

    2018-09-16

    #图论#poj#生成树#kruskal

  • POJ1258 Agri-Net 解题报告

    2018-09-16

    #图论#poj#prim#生成树

  • POJ 1274 The Perfect Stall 解题报告

    2018-09-16

    #二分图#最大匹配#poj#匈牙利算法

  • poj1284 欧拉函数的运用

    2018-09-16

    #最大公约数#数论#欧拉函数#poj#费马小定理

  • POJ1321 棋盘问题 解题报告

    2018-09-16

    #深度优先搜索#poj#搜索

  • POJ 1325 Machine Schedule 解题报告

    2018-09-16

    #图论#poj#最小覆盖点

  • POJ1390 Blocks 常见动态规划模型

    2018-09-16

    #动态规划#poj#DP

  • POJ1426 Find The Multiple 解题报告

    2018-09-16

    #深度优先搜索#数论#poj#搜索

  • poj1458 最长公共子序列问题

    2018-09-16

    #动态规划#poj#最长公共子序列

  • POJ 1469 COURSES 解题报告

    2018-09-16

    #二分图#图论#最大匹配#poj

  • poj1579 Function Run Fun 解题报告

    2018-09-16

    #poj#记忆化搜索

  • POJ1681 Painter's Problem 解题报告

    2018-09-16

    #枚举#poj#位运算#高斯消元

  • POJ 1789 Truck History 解题报告

    2018-09-16

    #图论#poj#prim#生成树

  • POJ 1797 Heavy Transportation 解题报告

    2018-09-16

    #并查集#最短路#图论#poj#生成树

  • POJ1830 开关问题 解题报告

    2018-09-16

    #poj#位运算#高斯消元

  • poj2115 同余方程与扩展欧几里得

    2018-09-16

    #poj#中国剩余定理#同余方程#扩展欧几里得

  • POJ2249--一道简单的排列组合题

    2018-09-16

    #数论#poj#排列#组合数学

  • POJ2689 Prime Distance 素数筛选

    2018-09-15

    #素数#筛选#poj

  • POJ2251 Dungeon Master 解题报告

    2018-09-15

    #数据结构#广度优先搜索#poj#搜索#队列

  • POJ 2253 Frogger 解题报告

    2018-09-15

    #最短路#图论#poj#生成树

  • POJ2262Goldbach's Conjecture 简单的素数判定

    2018-09-15

    #素数#枚举#poj

  • 从poj2356来体会 抽屉原理 的妙用

    2018-09-15

    #数论#poj#抽屉原理

  • POJ2407Relatives --欧拉函数的简单运用

    2018-09-15

    #素数#欧拉函数#poj

  • poj2409 Let it Bead 解题报告

    2018-09-15

    #polya#poj#组合数学

  • poj2478 又一欧拉公式的运用

    2018-09-15

    #数论#欧拉函数#poj

  • poj2479与poj2593,同一道DP题

    2018-09-15

    #动态规划#poj

  • POJ 2485 Highways 解题报告

    2018-09-15

    #图论#poj#最小生成树

  • POJ2488 A Knight's Journey 解题报告

    2018-09-14

    #深度优先搜索#poj#搜索

  • poj 2492 并查集

    2018-09-14

    #数据结构#并查集#poj

  • POJ 2506 高精度+递推

    2018-09-14

    #递归#poj#高精度

  • poj2663 Tri Tiling 解题报告

    2018-09-14

    #递归#数论#poj

  • POJ 2773 互素问题

    2018-09-14

    #数论#素数#poj

  • poj 2891 Strange Way to Express Integers 扩展欧几里得

    2018-09-14

    #最大公约数#数论#poj#扩展欧几里得#欧几里得

  • POJ3009Curling 2.0解题报告

    2018-09-14

    #深度优先搜索#poj#搜索

  • poj3070来体会矩阵的妙用

    2018-09-14

    #矩阵#快速幂#poj#斐波那契数列

  • poj3090 欧拉函数与法雷级数

    2018-09-14

    #数论#欧拉函数#poj#法雷级数

  • POJ3185 The Water Bowls 解题报告

    2018-09-14

    #枚举#poj#位运算#高斯消元

  • poj3233 又见矩阵,不过是等比吗?

    2018-09-14

    #数论#矩阵#poj#分治

  • POJ3278 Catch That Cow 解题报告

    2018-09-14

    #数据结构#广度优先搜索#poj#搜索

  • poj3370同样的是抽屉原理

    2018-09-14

    #数论#poj#抽屉原理

  • USACO 2.2.2 Subset Sums解题报告

    2018-09-14

    #动态规划#递归#记忆化搜索#usaco

  • POJ测试数据及官方标程,你能HOLD住吗?

    2018-09-14

    #poj#测试数据

  • USACO 2.2.3 Runaround Numbers解题报告

    2018-09-14

    #枚举#usaco

  • USACO 2.2.4 Party Lamps 解题报告

    2018-09-14

    #枚举#规律#搜索#usaco

  • USACO 2.3.1 Longest Prefix 解题报告

    2018-09-14

    #动态规划#字典树#数据结构#usaco

  • USACO 2.3.2 Cow Pedigrees 解题报告

    2018-09-14

    #动态规划#usaco#二叉树

  • USACO 2.3.3 Zero Sum 解题报告

    2018-09-14

    #深度优先搜索#枚举#usaco

  • USACO 2.3.4 Money Systems 解题报告

    2018-09-14

    #动态规划#usaco

  • USACO 2.3.5 Controlling Companies 解题报告

    2018-09-14

    #图论#usaco

  • USACO 3.1.4 Shaping Regions 搜索+矩形切割

    2018-09-14

    #深度优先搜索#矩形#分治#usaco#矩形切割

  • USACO 3.1.5 Contact 解题报告

    2018-09-14

    #字典树#usaco

  • USACO 3.1.6 Stamps(动态规划)解题报告

    2018-09-14

    #动态规划#usaco#背包

  • USACO 3.2.1 Factorials 求n!最后非零数(初级)

    2018-09-14

    #数论#usaco#阶乘

  • USACO 3.2.2 Stringsobits 解题报告

    2018-09-14

    #组合数学#usaco

  • USACO 3.2.3 Spinning Wheels

    2018-09-14

    #枚举#usaco

  • USACO 3.2.4 Feed Ratios 解题报告

    2018-09-14

    #高斯消元#usaco

  • USACO 3.2.5 Magic Squares (BFS+康托展开)

    2018-09-14

    #广度优先搜索#usaco#康托展开

  • USACO 3.2.6 Sweet Butter(SPFA求最短路)

    2018-09-14

    #usaco#spfa

  • USACO 3.3.1 Riding The Fences 欧拉回路

    2018-09-14

    #usaco#欧拉回路

  • ZOJ 2562 More Divisors 反素数

    2018-09-14

    #素数#zoj#反素数

  • ZOJ 3574 Under Attack II解题报告

    2018-09-14

    #矩形#zoj#归并排序#逆序对

  • ZOJ月赛解题报告-ZOJ Monthly, February 2012(ZOJ3571-3580)

    2018-09-14

    #最大公约数#数论#矩阵#数据结构#zoj

  • weibo
  • github
小龙少,年二十有二。始从文,连考而不中。遂习武,练武场上发一矢,中鼓吏,逐之出。改学IT,自建一变量,用之,烫烫烫烫烫烫烫烫烫烫!