/
poj-2251-Dungeon Master（三维bfs最短路）.html
317 lines (284 loc) · 58.4 KB
/
poj-2251-Dungeon Master（三维bfs最短路）.html
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
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
<!DOCTYPE html><html class="theme-next pisces use-motion" lang="zh-CN"><head><meta name="generator" content="Hexo 3.9.0"><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=2"><meta name="theme-color" content="#222"><link rel="apple-touch-icon" sizes="180x180" href="/images/icons/favicon-48.png?v=6.7.0"><link rel="icon" type="image/png" sizes="32x32" href="/images/icons/favicon-32.png?v=6.7.0"><link rel="icon" type="image/png" sizes="16x16" href="/images/icons/favicon-16.png?v=6.7.0"><link rel="mask-icon" href="/images/icons/logo.svg?v=6.7.0" color="#222"><link rel="alternate" href="/atom.xml" title="菠菜眾長" type="application/atom+xml"><meta http-equiv="Cache-Control" content="no-transform"><meta http-equiv="Cache-Control" content="no-siteapp"><link href="/lib/fancybox/source/jquery.fancybox.css" rel="stylesheet" type="text/css"><link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css"><link href="/css/main.css?v=6.7.0" rel="stylesheet" type="text/css"><script type="text/javascript" id="hexo.configurations">var NexT=window.NexT||{},CONFIG={root:"/",scheme:"Pisces",version:"6.7.0",sidebar:{position:"left",display:"always",offset:12,b2t:!1,scrollpercent:!0,onmobile:!0},fancybox:!0,fastclick:!0,lazyload:!0,tabs:!0,motion:{enable:!0,async:!0,transition:{post_block:"fadeIn",post_header:"slideDownIn",post_body:"slideDownIn",coll_header:"slideLeftIn",sidebar:"slideUpIn"}},algolia:{applicationID:"",apiKey:"",indexName:"",hits:{per_page:10},labels:{input_placeholder:"Search for Posts",hits_empty:"We didn't find any results for the search: ${query}",hits_stats:"${hits} results found in ${time} ms"}}}</script><meta name="baidu-site-verification" content="B2fOjPkYa7"><meta name="google-site-verification" content="OhdtVOx5uwpZ_mMm0AZJXzw-dY1PPpAAkdavmmQhIL4"><meta name="360-site-verification" content="5b1c9d7574859ca6e460dd687667d5dc"><meta name="shenma-site-verification" content="933461d02e7b7c40e5293ee90085127c_1569650330"><meta name="description" content="英文原题链接Description - 题目描述你被困在一个三维的空间中,现在要寻找最短路径逃生！空间由立方体单位构成你每次向上下前后左右移动一个单位需要一分钟你不能对角线移动并且四周封闭是否存在逃出生天的可能性？如果存在，则需要多少时间？Input - 输入输入第一行是一个数表示空间的数量。每个空间的描述的第一行为L，R和C（皆不超过30）。L表示空间的高度。R和C分别表示每层空间的行与列的大小"><meta name="keywords" content="ACM,C++,C,BFS,搜索,POJ"><meta property="og:type" content="article"><meta property="og:title" content="poj-2251-Dungeon Master（三维bfs最短路）"><meta property="og:url" content="https://lruihao.cn/posts/poj-2251-Dungeon Master（三维bfs最短路）.html"><meta property="og:site_name" content="菠菜眾長"><meta property="og:description" content="英文原题链接Description - 题目描述你被困在一个三维的空间中,现在要寻找最短路径逃生！空间由立方体单位构成你每次向上下前后左右移动一个单位需要一分钟你不能对角线移动并且四周封闭是否存在逃出生天的可能性？如果存在，则需要多少时间？Input - 输入输入第一行是一个数表示空间的数量。每个空间的描述的第一行为L，R和C（皆不超过30）。L表示空间的高度。R和C分别表示每层空间的行与列的大小"><meta property="og:locale" content="zh-CN"><meta property="og:updated_time" content="2019-03-28T15:15:06.510Z"><meta name="twitter:card" content="summary"><meta name="twitter:title" content="poj-2251-Dungeon Master（三维bfs最短路）"><meta name="twitter:description" content="英文原题链接Description - 题目描述你被困在一个三维的空间中,现在要寻找最短路径逃生！空间由立方体单位构成你每次向上下前后左右移动一个单位需要一分钟你不能对角线移动并且四周封闭是否存在逃出生天的可能性？如果存在，则需要多少时间？Input - 输入输入第一行是一个数表示空间的数量。每个空间的描述的第一行为L，R和C（皆不超过30）。L表示空间的高度。R和C分别表示每层空间的行与列的大小"><link rel="alternate" href="/atom.xml" title="菠菜眾長" type="application/atom+xml"><link rel="canonical" href="https://lruihao.cn/posts/poj-2251-Dungeon Master（三维bfs最短路）.html"><script type="text/javascript" id="page.configurations">CONFIG.page={sidebar:""}</script><title>poj-2251-Dungeon Master（三维bfs最短路） | 菠菜眾長</title><script type="text/javascript">var _hmt=_hmt||[];!function(){var e=document.createElement("script");e.src="https://hm.baidu.com/hm.js?d25f1e053205bf07562f33365fef04d7";var t=document.getElementsByTagName("script")[0];t.parentNode.insertBefore(e,t)}()</script><noscript><style type="text/css">.sidebar-inner,.use-motion .brand,.use-motion .collection-title,.use-motion .comments,.use-motion .menu-item,.use-motion .motion-element,.use-motion .pagination,.use-motion .post-block,.use-motion .post-body,.use-motion .post-header{opacity:initial}.use-motion .logo,.use-motion .site-subtitle,.use-motion .site-title{opacity:initial;top:initial}.logo-line-after i{right:initial}</style></noscript></head><body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN"><div class="container sidebar-position-left page-post-detail"><div class="headband"></div><header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="header-inner"><div class="site-brand-wrapper"><div class="site-meta"><div class="custom-logo-site-title"><a href="/" class="brand" rel="start"><span class="logo-line-before"><i></i></span> <span class="site-title">菠菜众长</span> <span class="logo-line-after"><i></i></span></a></div><h1 class="site-subtitle" itemprop="description">李瑞豪的博客</h1></div><div class="site-nav-toggle"><button aria-label="切换导航栏"><span class="btn-bar"></span> <span class="btn-bar"></span> <span class="btn-bar"></span></button></div></div><nav class="site-nav"><ul id="menu" class="menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i><br>首页</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i><br>归档<span class="badge">173</span></a></li><li class="menu-item menu-item-docs"><a href="/docs/" rel="section"><i class="menu-item-icon fa fa-fw fa-book"></i><br>综合</a></li><li class="menu-item menu-item-album"><a href="https://img.lruihao.cn" rel="external nofollow noopener noreferrer" target="_blank"><i class="menu-item-icon fa fa-fw fa-image"></i><br>相册</a></li><li class="menu-item menu-item-guestbook"><a href="/guestbook/" rel="section"><i class="menu-item-icon fa fa-fw fa-comments"></i><br>留言</a></li><li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="menu-item-icon fa fa-fw fa-address-card"></i><br>关于</a></li><li class="menu-item menu-item-search"><a href="javascript:;" class="popup-trigger"><i class="menu-item-icon fa fa-search fa-fw"></i><br>搜索</a></li></ul><div class="site-search"><div class="popup search-popup local-search-popup"><div class="local-search-header clearfix"><span class="search-icon"><i class="fa fa-search"></i> </span><span class="popup-btn-close"><i class="fa fa-times-circle"></i></span><div class="local-search-input-wrapper"><input autocomplete="off" placeholder="搜索..." spellcheck="false" type="text" id="local-search-input"></div></div><div id="local-search-result"><div style="text-align:center;padding:3px 0 0"><div style="margin-top:20px;font-size:18px;font-weight:600;border-bottom:1px solid #ccc"><i class="fa fa-history" aria-hidden="true"></i> 近期文章</div><ul style="margin:0;padding:0;list-style:none"><li><a href="/posts/year-2019.html" title="2019年度总结" target="_blank">2019年度总结</a></li><li><a href="/posts/sql.html" title="SQL总结" target="_blank">SQL总结</a></li><li><a href="/posts/cos-album.html" title="利用腾讯云为静态页面添加“动态”相册" target="_blank">利用腾讯云为静态页面添加“动态”相册</a></li><li><a href="/posts/restful.html" title="RESTful" target="_blank">RESTful</a></li><li><a href="/posts/phpPushUrl.html" title="php同时主动推送链接到百度，神马等站长平台" target="_blank">php同时主动推送链接到百度，神马等站长平台</a></li><li><a href="/posts/phpfile.html" title="php按行读取文件信息" target="_blank">php按行读取文件信息</a></li><li><a href="/posts/site-time.html" title="设置网站运行时间" target="_blank">设置网站运行时间</a></li><li><a href="/posts/async-defer.html" title="script的三种加载方式（async、defer）" target="_blank">script的三种加载方式（async、defer）</a></li><li><a href="/posts/Sublime-Text3.html" title="Sublime Text3快捷键大全" target="_blank">Sublime Text3快捷键大全</a></li><li><a href="/posts/netBeans.html" title="netBeans IDE开发设置" target="_blank">netBeans IDE开发设置</a></li><li><a href="/posts/dev-rules.html" title="web开发规则，代码规范" target="_blank">web开发规则，代码规范</a></li><li><a href="/posts/phpform.html" title="简单评论模块--php表单练习" target="_blank">简单评论模块--php表单练习</a></li><li><a href="/posts/phpfunc.html" title="php函数学习" target="_blank">php函数学习</a></li><li><a href="/posts/wamproot.html" title="WAMPServer自定义网站根目录等设置" target="_blank">WAMPServer自定义网站根目录等设置</a></li><li><a href="/posts/pysx2.html" title="python实训总结Ⅱ" target="_blank">python实训总结Ⅱ</a></li></ul></div></div></div></div></nav></div></header><a href="https://github.com/Lruihao/lruihao.github.io" class="github-corner" target="_blank" title="万水千山总是情,给个star行不行！" aria-label="万水千山总是情,给个star行不行！" rel="external nofollow noopener noreferrer"><svg width="80" height="80" viewbox="0 0 250 250" style="fill:#222;color:#fff;position:absolute;top:0;border:0;right:0" aria-hidden="true"><path d="M0,0 L115,115 L130,115 L142,142 L250,250 L250,0 Z"/><path d="M128.3,109.0 C113.8,99.7 119.0,89.6 119.0,89.6 C122.0,82.7 120.5,78.6 120.5,78.6 C119.2,72.0 123.4,76.3 123.4,76.3 C127.3,80.9 125.5,87.3 125.5,87.3 C122.9,97.6 130.6,101.9 134.4,103.2" fill="currentColor" style="transform-origin:130px 106px" class="octo-arm"/><path d="M115.0,115.0 C114.9,115.1 118.7,116.5 119.8,115.4 L133.7,101.6 C136.9,99.2 139.9,98.4 142.2,98.6 C133.8,88.0 127.5,74.4 143.8,58.0 C148.5,53.4 154.0,51.2 159.7,51.0 C160.3,49.4 163.2,43.6 171.4,40.1 C171.4,40.1 176.1,42.5 178.8,56.2 C183.1,58.6 187.2,61.8 190.9,65.4 C194.5,69.0 197.7,73.2 200.1,77.6 C213.8,80.2 216.3,84.9 216.3,84.9 C212.7,93.1 206.9,96.0 205.4,96.6 C205.1,102.4 203.0,107.8 198.3,112.5 C181.9,128.9 168.3,122.5 157.7,114.1 C157.9,116.9 156.7,120.9 152.7,124.9 L141.0,136.5 C139.8,137.7 141.6,141.9 141.8,141.8 Z" fill="currentColor" class="octo-body"/></svg></a><main id="main" class="main"><div class="main-inner"><div class="content-wrap"><div id="content" class="content"><div id="posts" class="posts-expand"><div class="reading-progress-bar"></div><article class="post post-type-normal" itemscope itemtype="http://schema.org/Article"><div class="post-block"><link itemprop="mainEntityOfPage" href="https://lruihao.cn/posts/poj-2251-Dungeon Master（三维bfs最短路）.html"><span hidden itemprop="author" itemscope itemtype="http://schema.org/Person"><meta itemprop="name" content="李瑞豪"><meta itemprop="description" content="从ACM到Web，分享程序、技巧、干货，记录心情、学习、成长！"><meta itemprop="image" content="/images/avatar.png"></span><span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization"><meta itemprop="name" content="菠菜眾長"></span><header class="post-header"><h2 class="post-title" itemprop="name headline">poj-2251-Dungeon Master（三维bfs最短路）<a href="https://github.com/Lruihao/lruihao.github.io/tree/hexo/source/_posts/poj-2251-Dungeon Master（三维bfs最短路）.md" class="post-edit-link" title="编辑" rel="external nofollow noopener noreferrer" target="_blank"><i class="fa fa-pencil"></i></a></h2><div class="post-meta"><span class="post-time"><span class="post-meta-item-icon"><i class="fa fa-calendar-o"></i> </span><span class="post-meta-item-text">发表于</span> <time title="创建时间：2018-07-22 12:02:32" itemprop="dateCreated datePublished" datetime="2018-07-22T12:02:32+08:00">2018-07-22</time> </span><span class="post-category"><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-folder-o"></i> </span><span class="post-meta-item-text">分类于</span> <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/ACM/" itemprop="url" rel="index"><span itemprop="name">ACM</span></a></span> ， <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/ACM/搜索/" itemprop="url" rel="index"><span itemprop="name">搜索</span></a></span> </span><span class="post-comments-count"><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-comment-o"></i> </span><span class="post-meta-item-text">评论数： </span><a href="/posts/poj-2251-Dungeon Master（三维bfs最短路）.html#comments" itemprop="discussionUrl"><span class="post-comments-count valine-comment-count" data-xid="/posts/poj-2251-Dungeon Master（三维bfs最短路）.html" itemprop="commentCount"></span> </a></span><span id="/posts/poj-2251-Dungeon Master（三维bfs最短路）.html" class="leancloud_visitors" data-flag-title="poj-2251-Dungeon Master（三维bfs最短路）"><span class="post-meta-divider">|</span> <span title="阅读次数"><span class="post-meta-item-icon"><i class="fa fa-eye"></i> </span><span class="post-meta-item-text">阅读次数：</span> <span class="leancloud-visitors-count"></span></span></span><div class="post-symbolscount"><span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-file-word-o"></i> </span><span class="post-meta-item-text">本文字数：</span> <span title="本文字数">785</span> <span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-clock-o"></i> </span><span class="post-meta-item-text">阅读时长 ≈</span> <span title="阅读时长">3 分钟</span></div></div></header><div class="post-body" itemprop="articleBody"><p><a href="http://poj.org/problem?id=2251" rel="external nofollow noopener noreferrer" target="_blank">英文原题链接</a></p><h3 id="Description-题目描述"><a href="#Description-题目描述" class="headerlink" title="Description - 题目描述"></a>Description - 题目描述</h3><p>你被困在一个三维的空间中,现在要寻找最短路径逃生！<br>空间由立方体单位构成<br>你每次向上下前后左右移动一个单位需要一分钟<br>你不能对角线移动并且四周封闭<br>是否存在逃出生天的可能性？如果存在，则需要多少时间？</p><h3 id="Input-输入"><a href="#Input-输入" class="headerlink" title="Input - 输入"></a>Input - 输入</h3><p>输入第一行是一个数表示空间的数量。<br>每个空间的描述的第一行为L，R和C（皆不超过30）。<br>L表示空间的高度。R和C分别表示每层空间的行与列的大小。<br>随后L层地牢，每层R行，每行C个字符。<br>每个字符表示空间的一个单元。’#’表示不可通过单元，’.’表示空白单元。你的起始位置在’S’，出口为’E’。<br>每层空间后都有一个空行。L，R和C均为0时输入结束。</p><h3 id="Output-输出"><a href="#Output-输出" class="headerlink" title="Output - 输出"></a>Output - 输出</h3><p>每个空间对应一行输出。<br>如果可以逃生，则输出如下<br>Escaped in x minute(s).</p><p> x为最短脱离时间。</p><p>如果无法逃生，则输出如下</p><p>Trapped!</p><h3 id="Sample-Input-输入样例"><a href="#Sample-Input-输入样例" class="headerlink" title="Sample Input - 输入样例"></a>Sample Input - 输入样例</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line">3 4 5</span><br><span class="line">S....</span><br><span class="line">.###.</span><br><span class="line">.##..</span><br><span class="line">###.#</span><br><span class="line"></span><br><span class="line">#####</span><br><span class="line">#####</span><br><span class="line">##.##</span><br><span class="line">##...</span><br><span class="line"></span><br><span class="line">#####</span><br><span class="line">#####</span><br><span class="line">#.###</span><br><span class="line">####E</span><br><span class="line"></span><br><span class="line">1 3 3</span><br><span class="line">S##</span><br><span class="line">#E#</span><br><span class="line">###</span><br><span class="line"></span><br><span class="line">0 0 0</span><br></pre></td></tr></table></figure><h3 id="Sample-Output-输出样例"><a href="#Sample-Output-输出样例" class="headerlink" title="Sample Output - 输出样例"></a>Sample Output - 输出样例</h3><p>Escaped in 11 minute(s).<br>Trapped!</p><p>类似二维四个方向的bfs最短路，改成上下东西南北就行了，三维bfs最短路<br></p><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><queue></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><algorithm></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">char</span> <span class="built_in">map</span>[<span class="number">35</span>][<span class="number">35</span>][<span class="number">35</span>];</span><br><span class="line"><span class="keyword">int</span> vis[<span class="number">35</span>][<span class="number">35</span>][<span class="number">35</span>];</span><br><span class="line"><span class="keyword">int</span> k,n,m,sx,sy,sz,ex,ey,ez;</span><br><span class="line"><span class="keyword">int</span> to[<span class="number">6</span>][<span class="number">3</span>] = {{<span class="number">0</span>,<span class="number">0</span>,<span class="number">1</span>},{<span class="number">0</span>,<span class="number">0</span>,<span class="number">-1</span>},{<span class="number">0</span>,<span class="number">1</span>,<span class="number">0</span>},{<span class="number">0</span>,<span class="number">-1</span>,<span class="number">0</span>},{<span class="number">1</span>,<span class="number">0</span>,<span class="number">0</span>},{<span class="number">-1</span>,<span class="number">0</span>,<span class="number">0</span>}};<span class="comment">//上下东西南北</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> x,y,z,step;</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">check</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> y,<span class="keyword">int</span> z)</span><span class="comment">//检查是否可走</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span>(x<<span class="number">0</span> || y<<span class="number">0</span> || z<<span class="number">0</span> || x>=k || y>=n || z>=m)<span class="comment">//越界判断</span></span><br><span class="line"> <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">map</span>[x][y][z] == <span class="string">'#'</span>)</span><br><span class="line"> <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(vis[x][y][z])</span><br><span class="line"> <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">bfs</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> i;</span><br><span class="line"> node a,next;</span><br><span class="line"> <span class="built_in">queue</span><node> Q;</span><br><span class="line"> a.x = sx,a.y = sy,a.z = sz;</span><br><span class="line"> a.step = <span class="number">0</span>;</span><br><span class="line"> vis[sx][sy][sz] = <span class="number">1</span>;</span><br><span class="line"> Q.push(a);</span><br><span class="line"> <span class="keyword">while</span>(!Q.empty())</span><br><span class="line"> {</span><br><span class="line"> a = Q.front();</span><br><span class="line"> Q.pop();</span><br><span class="line"> <span class="keyword">if</span>(a.x == ex && a.y == ey && a.z == ez)</span><br><span class="line"> <span class="keyword">return</span> a.step;</span><br><span class="line"> <span class="keyword">for</span>(i = <span class="number">0</span>; i<<span class="number">6</span>; i++)</span><br><span class="line"> {</span><br><span class="line"> next = a;</span><br><span class="line"> next.x = a.x+to[i][<span class="number">0</span>];</span><br><span class="line"> next.y = a.y+to[i][<span class="number">1</span>];</span><br><span class="line"> next.z = a.z+to[i][<span class="number">2</span>];</span><br><span class="line"> <span class="keyword">if</span>(check(next.x,next.y,next.z))</span><br><span class="line"> <span class="keyword">continue</span>;</span><br><span class="line"> vis[next.x][next.y][next.z] = <span class="number">1</span>;</span><br><span class="line"> next.step = a.step+<span class="number">1</span>;</span><br><span class="line"> Q.push(next);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> i,j,r;</span><br><span class="line"> <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">"%d%d%d"</span>,&k,&n,&m),n+m+k)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span>(i = <span class="number">0</span>; i<k; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span>(j = <span class="number">0</span>; j<n; j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%s"</span>,<span class="built_in">map</span>[i][j]);</span><br><span class="line"> <span class="keyword">for</span>(r = <span class="number">0</span>; r<m; r++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">map</span>[i][j][r] == <span class="string">'S'</span>)</span><br><span class="line"> {</span><br><span class="line"> sx = i,sy = j,sz = r;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(<span class="built_in">map</span>[i][j][r] == <span class="string">'E'</span>)</span><br><span class="line"> {</span><br><span class="line"> ex = i,ey = j,ez = r;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">memset</span>(vis,<span class="number">0</span>,<span class="keyword">sizeof</span>(vis));</span><br><span class="line"> <span class="keyword">int</span> ans;</span><br><span class="line"> ans = bfs();</span><br><span class="line"> <span class="keyword">if</span>(ans)</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"Escaped in %d minute(s).\n"</span>,ans);</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"Trapped!\n"</span>);</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure><p></p></div><div class="popular-posts-header"><i class="fa fa-link"></i> 相关文章</div><!--[if !IE]><!--><details><summary style="cursor:pointer">点击查看</summary><!--<![endif]--><ul class="popular-posts"><li class="popular-posts-item"><div class="popular-posts-title"><a href="\posts\深搜广搜.html" rel="bookmark">深搜广搜</a></div></li><li class="popular-posts-item"><div class="popular-posts-title"><a href="\posts\POJ - 3278 -Catch That Cow (bfs).html" rel="bookmark">POJ-3278-Catch That Cow(bfs)</a></div></li><li class="popular-posts-item"><div class="popular-posts-title"><a href="\posts\poj-3984-迷宫问题(bfs路径).html" rel="bookmark">poj-3984-迷宫问题(bfs路径)</a></div></li><li class="popular-posts-item"><div class="popular-posts-title"><a href="\posts\poj1797.html" rel="bookmark">Heavy Transportation-poj1797(dijkstra或最大生成树)</a></div></li><li class="popular-posts-item"><div class="popular-posts-title"><a href="\posts\poj1182.html" rel="bookmark">食物链-poj1182（带权并查集经典模板）</a></div></li><li class="popular-posts-item"><div class="popular-posts-title"><a href="\posts\The-suspects.html" rel="bookmark">The-suspects-POJ-1611(并查集)</a></div></li></ul><!--[if IE]><!--></details><!--<![endif]--><div><div style="padding:10px 0;margin:20px auto;width:90%;text-align:center"><div>欢迎关注公众号，感谢支持 ！</div><button id="rewardButton" disable="enable" onclick="var qr = document.getElementById("QR"); if (qr.style.display === 'none') {qr.style.display='block';} else {qr.style.display='none'}"><span>赞赏</span></button><div id="QR" style="display:none"><div id="wechat" style="display:inline-block"><img id="wechat_qr" src="/images/wechatpay.gif" alt="李瑞豪 微信支付"><p>微信支付</p></div><div id="alipay" style="display:inline-block"><img id="alipay_qr" src="/images/alipay.gif" alt="李瑞豪 支付宝"><p>支付宝</p></div></div></div></div><div class="copyright-box"><ul class="post-copyright"><li class="post-copyright-author"><strong>本文作者： </strong>李瑞豪</li><li><strong>修改时间： </strong>2019-03-28 23:15:06</li><li class="post-copyright-link"><strong>本文链接：</strong> <a href="https://lruihao.cn/posts/poj-2251-Dungeon Master（三维bfs最短路）.html" title="poj-2251-Dungeon Master（三维bfs最短路）">https://lruihao.cn/posts/poj-2251-Dungeon Master（三维bfs最短路）.html</a></li><li class="post-copyright-license"><strong>版权声明： </strong>本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" rel="external nofollow noopener noreferrer" target="_blank"><i class="fa fa-fw fa-creative-commons"></i> BY-NC-SA 4.0</a> 许可协议。转载请注明出处！</li></ul></div><div class="post-tags"><a href="/tags/ACM/" rel="tag"><i class="fa fa-tag"></i> ACM</a> <a href="/tags/C/" rel="tag"><i class="fa fa-tag"></i> C++</a> <a href="/tags/C/" rel="tag"><i class="fa fa-tag"></i> C</a> <a href="/tags/BFS/" rel="tag"><i class="fa fa-tag"></i> BFS</a> <a href="/tags/搜索/" rel="tag"><i class="fa fa-tag"></i> 搜索</a> <a href="/tags/POJ/" rel="tag"><i class="fa fa-tag"></i> POJ</a></div><footer class="post-footer"><div class="post-nav"><div class="post-nav-next post-nav-item"><a href="/posts/poj-1321 棋盘问题（dfs）.html" rel="next" title="poj-1321 棋盘问题（dfs）"><i class="fa fa-chevron-left"></i> poj-1321 棋盘问题（dfs）</a></div><span class="post-nav-divider"></span><div class="post-nav-prev post-nav-item"><a href="/posts/POJ - 3278 -Catch That Cow (bfs).html" rel="prev" title="POJ-3278-Catch That Cow(bfs)">POJ-3278-Catch That Cow(bfs) <i class="fa fa-chevron-right"></i></a></div></div></footer></div></article></div></div><div class="comments" id="comments"></div></div><div class="sidebar-toggle"><div class="sidebar-toggle-line-wrap"><span class="sidebar-toggle-line sidebar-toggle-line-first"></span> <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span> <span class="sidebar-toggle-line sidebar-toggle-line-last"></span></div></div><aside id="sidebar" class="sidebar"><div id="sidebar-dimmer"></div><div class="sidebar-inner"><ul class="sidebar-nav motion-element"><li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">文章目录</li><li class="sidebar-nav-overview" data-target="site-overview-wrap">站点概览</li></ul><div class="site-overview-wrap sidebar-panel"><div class="site-overview"><div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person"><img class="site-author-image" itemprop="image" src="/images/avatar.png" alt="李瑞豪"><p class="site-author-name" itemprop="name">李瑞豪</p><p class="site-description motion-element" itemprop="description">从ACM到Web，分享程序、技巧、干货，记录心情、学习、成长！</p></div><nav class="site-state motion-element"><div class="site-state-item site-state-posts"><a href="/archives/"><span class="site-state-item-count">173</span> <span class="site-state-item-name">日志</span></a></div><div class="site-state-item site-state-categories"><a href="/docs/categories/index.html"><span class="site-state-item-count">25</span> <span class="site-state-item-name">分类</span></a></div><div class="site-state-item site-state-tags"><a href="/docs/tags/index.html"><span class="site-state-item-count">122</span> <span class="site-state-item-name">标签</span></a></div></nav><div class="feed-link motion-element"><a href="/atom.xml" rel="alternate"><i class="fa fa-rss"></i> RSS</a></div><div class="links-of-author motion-element"><span class="links-of-author-item"><a href="https://github.com/Lruihao" title="GitHub → https://github.com/Lruihao" rel="external nofollow noopener noreferrer" target="_blank"><i class="fa fa-fw fa-github"></i></a> </span><span class="links-of-author-item"><a href="https://blog.csdn.net/qq_39520417" title="CSDN → https://blog.csdn.net/qq_39520417" rel="external nofollow noopener noreferrer" target="_blank"><i class="fa fa-fw fa-contao"></i></a> </span><span class="links-of-author-item"><a href="https://weibo.com/liahao" title="微博 → https://weibo.com/liahao" rel="external nofollow noopener noreferrer" target="_blank"><i class="fa fa-fw fa-weibo"></i></a> </span><span class="links-of-author-item"><a href="/images/qq.jpg" title="QQ → /images/qq.jpg"><i class="fa fa-fw fa-qq"></i></a> </span><span class="links-of-author-item"><a href="mailto:1074627678@qq.com" title="E-Mail → mailto:1074627678@qq.com" rel="external nofollow noopener noreferrer" target="_blank"><i class="fa fa-fw fa-envelope"></i></a></span></div><div class="cc-license motion-element" itemprop="license"><a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" class="cc-opacity" rel="external nofollow noopener noreferrer" target="_blank"><img src="/images/cc-by-nc-sa.svg" alt="Creative Commons"></a></div><div class="links-of-blogroll motion-element links-of-blogroll-inline"><div class="links-of-blogroll-title"><i class="fa fa-fw fa-globe"></i> 书签</div><ul class="links-of-blogroll-list"><li class="links-of-blogroll-item"><a href="/docs/donators/" title="/docs/donators/">赞助记录</a> </li><li class="links-of-blogroll-item"><a href="/docs/friends/" title="/docs/friends/">友情链接</a> </li><li class="links-of-blogroll-item"><a href="/posts/links.html" title="/posts/links.html">收藏夹</a> </li><li class="links-of-blogroll-item"><a href="/posts/font-mmt.html" title="/posts/font-mmt.html">MMT</a> </li><li class="links-of-blogroll-item"><a href="http://md.lruihao.cn" title="http://md.lruihao.cn" rel="external nofollow noopener noreferrer" target="_blank">WXMD</a> </li><li class="links-of-blogroll-item"><a href="/posts/webbiji.html" title="/posts/webbiji.html">WEB</a> </li></ul></div><iframe scrolling="no" src="https://tianqiapi.com/api.php?appid=72515596&appsecret=XDyzr75j&style=ta&skin=grape&align=center&fontsize=10&paddingtop=5&color=2f4f4f" frameborder="0" width="100%" height="20px" allowtransparency="true"></iframe></div></div><div class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active"><div class="post-toc"><div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-3"><a class="nav-link" href="#Description-题目描述"><span class="nav-number">1.</span> <span class="nav-text">Description - 题目描述</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Input-输入"><span class="nav-number">2.</span> <span class="nav-text">Input - 输入</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Output-输出"><span class="nav-number">3.</span> <span class="nav-text">Output - 输出</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Sample-Input-输入样例"><span class="nav-number">4.</span> <span class="nav-text">Sample Input - 输入样例</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#Sample-Output-输出样例"><span class="nav-number">5.</span> <span class="nav-text">Sample Output - 输出样例</span></a></li></ol></div></div></div></div></aside></div></main><footer id="footer" class="footer"><div class="footer-inner"><div class="copyright">Copyright © 2018 – <span itemprop="copyrightYear">2020</span> <span class="with-love" id="animate"><i class="fa fa-heartbeat"></i> </span><span class="author" itemprop="copyrightHolder">LRH. </span> <span title="博客总字数"><i class="fa fa-edit"></i> <span class="post-count">114.4k</span>字</span></div><div class="busuanzi-count"><script async src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script><span class="post-meta-item-icon"><i class="fa fa-user"></i> </span><span class="site-uv" title="总访客量"><span class="busuanzi-value" id="busuanzi_value_site_uv"><i class="fa fa-spinner fa-spin"></i></span> 人次 </span><span class="post-meta-divider">|</span> <span class="run-times" title="网站运行时间">载入天数时分秒...</span> <span class="post-meta-divider">|</span> <span class="post-meta-item-icon"><i class="fa fa-eye"></i> </span><span class="site-pv" title="总访问量"><span class="busuanzi-value" id="busuanzi_value_site_pv"><i class="fa fa-spinner fa-spin"></i></span> 次</span></div><div class="weixin-box"><div class="weixin-menu"><div class="weixin-hover"><div class="weixin-description">微信扫一扫，订阅本博客</div></div></div></div><div class="beian" style="display:inline-block;height:20px;line-height:20px"><a target="_blank" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=43030402000254" rel="external nofollow noopener noreferrer"><img src="/images/gov.png" style="float:left" alt="公安">湘公网安备43030402000254号</a> <span class="post-meta-divider" style="color:#555">|</span> <span><a href="http://www.beian.miit.gov.cn" target="_blank" rel="external nofollow noopener noreferrer">湘ICP备18020535号</a></span></div></div></footer><div class="back-to-top"><i class="fa fa-arrow-up"></i> <span id="scrollpercent"><span>0</span>%</span></div></div><script type="text/javascript">"[object Function]"!==Object.prototype.toString.call(window.Promise)&&(window.Promise=null)</script><script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script><script type="text/javascript" src="/lib/fastclick/lib/fastclick.min.js?v=1.0.6"></script><script type="text/javascript" src="/lib/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script><script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script><script type="text/javascript" src="/lib/fancybox/source/jquery.fancybox.pack.js"></script><script type="text/javascript" src="/lib/reading_progress/reading_progress.js"></script><script type="text/javascript" src="/js/src/utils.js?v=6.7.0"></script><script type="text/javascript" src="/js/src/motion.js?v=6.7.0"></script><script type="text/javascript" src="/js/src/affix.js?v=6.7.0"></script><script type="text/javascript" src="/js/src/schemes/pisces.js?v=6.7.0"></script><script type="text/javascript" src="/js/src/scrollspy.js?v=6.7.0"></script><script type="text/javascript" src="/js/src/post-details.js?v=6.7.0"></script><script type="text/javascript" src="/js/src/bootstrap.js?v=6.7.0"></script><script>$(".highlight").each(function(t,e){var n=$("<div>").addClass("highlight-wrap");$(e).after(n),n.append($("<button>").addClass("copy-btn").append("复制").on("click",function(t){var e=$(this).parent().find(".code").find(".line").map(function(t,e){return $(e).text()}).toArray().join("\n"),n=document.createElement("textarea");document.body.appendChild(n),n.style.position="absolute",n.style.top="0px",n.style.left="0px",n.value=e,n.select(),n.focus();var o=document.execCommand("copy");document.body.removeChild(n),o?$(this).text("复制成功"):$(this).text("复制失败"),$(this).blur()})).on("mouseleave",function(t){var e=$(this).find(".copy-btn");setTimeout(function(){e.text("复制")},300)}).append(e)})</script><script>$("body").find("pre.mermaid").length&&$.ajax({type:"GET",url:"//cdn.jsdelivr.net/npm/mermaid@8/dist/mermaid.min.js",dataType:"script",cache:!0,success:function(){mermaid.initialize({theme:"forest",logLevel:3,flowchart:{curve:"linear"},gantt:{axisFormat:"%m/%d/%Y"},sequence:{actorMargin:50}})}})</script><script>function createTime(){var e=new Date,t=new Date("05/28/2018 20:01:01"),n=(e-t)/1e3,i=Math.floor(n/60/60/24),r=Math.floor(n/60/60-24*i),h=Math.floor(n/60-1440*i-60*r),a=Math.floor((e-t)/1e3-86400*i-3600*r-60*h);1===String(r).length&&(r="0"+r),1===String(h).length&&(h="0"+h),1===String(a).length&&(a="0"+a),document.querySelector(".run-times").innerHTML=i+" 天 "+r+" 时 "+h+" 分 "+a+" 秒"}if(document.hidden)clearInterval(siteTime);else var siteTime=setInterval("createTime()",500)</script><script type="text/javascript" src="/js/src/console.js"></script><script async type="text/javascript" src="/js/src/night.js"></script><div class="cover"></div><script async type="text/javascript" src="/js/src/crash-cheat.js"></script><script src="/js/src/activate-power-mode.js"></script><script>POWERMODE.colorful=!0,POWERMODE.shake=!1,document.body.addEventListener("input",POWERMODE)</script><script type="text/javascript" src="/js/src/love.js"></script><script type="text/javascript" src="/js/src/link-card.js" defer></script><script type="text/javascript" src="/js/src/pageQRcode.js" defer></script><script src="//cdn1.lncld.net/static/js/3.11.1/av-min.js"></script><script src="//unpkg.com/valine/dist/Valine.min.js"></script><script>var GUEST=["nick","mail","link"],guest="nick,mail,link";guest=guest.split(",").filter(function(e){return-1<GUEST.indexOf(e)}),new Valine({el:"#comments",verify:!1,notify:!1,appId:"7HwTRT0Q0Tfrat6ugrT6P67c-gzGzoHsz",appKey:"mhTY1kuUmviCtQwkwOASfsfD",placeholder:"ヾﾉ≧∀≦)o~ 有事请留言！\n评论功能以邮件作为通知方式！\n如有必要请填写正确邮箱！",avatar:"wavatar",meta:guest,pageSize:"10",visitor:!0,lang:"zh-cn"})</script><script type="text/javascript">// Popup Window;
var isfetched = false;
var isXml = true;
// Search DB path;
var search_path = "search.xml";
if (search_path.length === 0) {
search_path = "search.xml";
} else if (/json$/i.test(search_path)) {
isXml = false;
}
var path = "/" + search_path;
// monitor main search box;
var onPopupClose = function (e) {
$('.popup').hide();
$('#local-search-input').val('');
$('.search-result-list').remove();
$('#no-result').remove();
$(".local-search-pop-overlay").remove();
$('body').css('overflow', '');
}
function proceedsearch() {
$("body")
.append('<div class="search-popup-overlay local-search-pop-overlay"></div>')
.css('overflow', 'hidden');
$('.search-popup-overlay').click(onPopupClose);
$('.popup').toggle();
var $localSearchInput = $('#local-search-input');
$localSearchInput.attr("autocapitalize", "none");
$localSearchInput.attr("autocorrect", "off");
$localSearchInput.focus();
}
// search function;
var searchFunc = function(path, search_id, content_id) {
'use strict';
// start loading animation
$("body")
.append('<div class="search-popup-overlay local-search-pop-overlay">' +
'<div id="search-loading-icon">' +
'<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>' +
'</div>' +
'</div>')
.css('overflow', 'hidden');
$("#search-loading-icon").css('margin', '20% auto 0 auto').css('text-align', 'center');
$.ajax({
url: path,
dataType: isXml ? "xml" : "json",
async: true,
success: function(res) {
// get the contents from search data
isfetched = true;
$('.popup').detach().appendTo('.header-inner');
var datas = isXml ? $("entry", res).map(function() {
return {
title: $("title", this).text(),
content: $("content",this).text(),
url: $("url" , this).text()
};
}).get() : res;
var input = document.getElementById(search_id);
var resultContent = document.getElementById(content_id);
var inputEventFunction = function() {
var searchText = input.value.trim().toLowerCase();
var keywords = searchText.split(/[\s\-]+/);
if (keywords.length > 1) {
keywords.push(searchText);
}
var resultItems = [];
if (searchText.length > 0) {
// perform local searching
datas.forEach(function(data) {
var isMatch = false;
var hitCount = 0;
var searchTextCount = 0;
var title = data.title.trim();
var titleInLowerCase = title.toLowerCase();
var content = data.content.trim().replace(/<[^>]+>/g,"");
var contentInLowerCase = content.toLowerCase();
var articleUrl = decodeURIComponent(data.url);
var indexOfTitle = [];
var indexOfContent = [];
// only match articles with not empty titles
if(title != '') {
keywords.forEach(function(keyword) {
function getIndexByWord(word, text, caseSensitive) {
var wordLen = word.length;
if (wordLen === 0) {
return [];
}
var startPosition = 0, position = [], index = [];
if (!caseSensitive) {
text = text.toLowerCase();
word = word.toLowerCase();
}
while ((position = text.indexOf(word, startPosition)) > -1) {
index.push({position: position, word: word});
startPosition = position + wordLen;
}
return index;
}
indexOfTitle = indexOfTitle.concat(getIndexByWord(keyword, titleInLowerCase, false));
indexOfContent = indexOfContent.concat(getIndexByWord(keyword, contentInLowerCase, false));
});
if (indexOfTitle.length > 0 || indexOfContent.length > 0) {
isMatch = true;
hitCount = indexOfTitle.length + indexOfContent.length;
}
}
// show search results
if (isMatch) {
// sort index by position of keyword
[indexOfTitle, indexOfContent].forEach(function (index) {
index.sort(function (itemLeft, itemRight) {
if (itemRight.position !== itemLeft.position) {
return itemRight.position - itemLeft.position;
} else {
return itemLeft.word.length - itemRight.word.length;
}
});
});
// merge hits into slices
function mergeIntoSlice(text, start, end, index) {
var item = index[index.length - 1];
var position = item.position;
var word = item.word;
var hits = [];
var searchTextCountInSlice = 0;
while (position + word.length <= end && index.length != 0) {
if (word === searchText) {
searchTextCountInSlice++;
}
hits.push({position: position, length: word.length});
var wordEnd = position + word.length;
// move to next position of hit
index.pop();
while (index.length != 0) {
item = index[index.length - 1];
position = item.position;
word = item.word;
if (wordEnd > position) {
index.pop();
} else {
break;
}
}
}
searchTextCount += searchTextCountInSlice;
return {
hits: hits,
start: start,
end: end,
searchTextCount: searchTextCountInSlice
};
}
var slicesOfTitle = [];
if (indexOfTitle.length != 0) {
slicesOfTitle.push(mergeIntoSlice(title, 0, title.length, indexOfTitle));
}
var slicesOfContent = [];
while (indexOfContent.length != 0) {
var item = indexOfContent[indexOfContent.length - 1];
var position = item.position;
var word = item.word;
// cut out 100 characters
var start = position - 20;
var end = position + 80;
if(start < 0){
start = 0;
}
if (end < position + word.length) {
end = position + word.length;
}
if(end > content.length){
end = content.length;
}
slicesOfContent.push(mergeIntoSlice(content, start, end, indexOfContent));
}
// sort slices in content by search text's count and hits' count
slicesOfContent.sort(function (sliceLeft, sliceRight) {
if (sliceLeft.searchTextCount !== sliceRight.searchTextCount) {
return sliceRight.searchTextCount - sliceLeft.searchTextCount;
} else if (sliceLeft.hits.length !== sliceRight.hits.length) {
return sliceRight.hits.length - sliceLeft.hits.length;
} else {
return sliceLeft.start - sliceRight.start;
}
});
// select top N slices in content
var upperBound = parseInt('1');
if (upperBound >= 0) {
slicesOfContent = slicesOfContent.slice(0, upperBound);
}
// highlight title and content
function highlightKeyword(text, slice) {
var result = '';
var prevEnd = slice.start;
slice.hits.forEach(function (hit) {
result += text.substring(prevEnd, hit.position);
var end = hit.position + hit.length;
result += '<b class="search-keyword">' + text.substring(hit.position, end) + '</b>';
prevEnd = end;
});
result += text.substring(prevEnd, slice.end);
return result;
}
var resultItem = '';
if (slicesOfTitle.length != 0) {
resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + highlightKeyword(title, slicesOfTitle[0]) + "</a>";
} else {
resultItem += "<li><a href='" + articleUrl + "' class='search-result-title'>" + title + "</a>";
}
slicesOfContent.forEach(function (slice) {
resultItem += "<a href='" + articleUrl + "'>" +
"<p class=\"search-result\">" + highlightKeyword(content, slice) +
"...</p>" + "</a>";
});
resultItem += "</li>";
resultItems.push({
item: resultItem,
searchTextCount: searchTextCount,
hitCount: hitCount,
id: resultItems.length
});
}
})
};
if (keywords.length === 1 && keywords[0] === "") {
resultContent.innerHTML = '<div id="no-result"><i class="fa fa-search fa-5x" /></div>'
} else if (resultItems.length === 0) {
resultContent.innerHTML = '<div id="no-result"><i class="fa fa-frown-o fa-5x" /></div>'
} else {
resultItems.sort(function (resultLeft, resultRight) {
if (resultLeft.searchTextCount !== resultRight.searchTextCount) {
return resultRight.searchTextCount - resultLeft.searchTextCount;
} else if (resultLeft.hitCount !== resultRight.hitCount) {
return resultRight.hitCount - resultLeft.hitCount;
} else {
return resultRight.id - resultLeft.id;
}
});
var searchResultList = '<ul class=\"search-result-list\">';
resultItems.forEach(function (result) {
searchResultList += result.item;
})
searchResultList += "</ul>";
resultContent.innerHTML = searchResultList;
}
}
if ('auto' === 'auto') {
input.addEventListener('input', inputEventFunction);
} else {
$('.search-icon').click(inputEventFunction);
input.addEventListener('keypress', function (event) {
if (event.keyCode === 13) {
inputEventFunction();
}
});
}
// remove loading animation
$(".local-search-pop-overlay").remove();
$('body').css('overflow', '');
proceedsearch();
}
});
}
// handle and trigger popup window;
$('.popup-trigger').click(function(e) {
e.stopPropagation();
if (isfetched === false) {
searchFunc(path, 'local-search-input', 'local-search-result');
} else {
proceedsearch();
};
});
$('.popup-btn-close').click(onPopupClose);
$('.popup').click(function(e){
e.stopPropagation();
});
$(document).on('keyup', function (event) {
var shouldDismissSearchPopup = event.which === 27 &&
$('.search-popup').is(':visible');
if (shouldDismissSearchPopup) {
onPopupClose();
}
});</script><script>!function(){var t=document.createElement("script"),e=window.location.protocol.split(":")[0];t.src="https"===e?"https://zz.bdstatic.com/linksubmit/push.js":"http://push.zhanzhang.baidu.com/push.js";var s=document.getElementsByTagName("script")[0];s.parentNode.insertBefore(t,s)}()</script><script src="/lib/pangu/dist/pangu.min.js?v=3.3"></script><script type="text/javascript">pangu.spacingPage()</script><script src="/lib/bookmark/bookmark.min.js?v=1.0"></script><script type="text/javascript">bookmark.scrollToMark("manual","#更多")</script><script>!function(e){var r=Array.prototype.slice.call(document.querySelectorAll("img[data-original]"));function t(){for(var c=0;c<r.length;c++)t=r[c],void 0,0<=(n=t.getBoundingClientRect()).top&&0<=n.left&&n.top<=(e.innerHeight||document.documentElement.clientHeight)&&function(){var t,n,e,i,o=r[c];t=o,n=function(){r=r.filter(function(t){return o!==t})},e=new Image,i=t.getAttribute("data-original"),e.onload=function(){t.src=i,n&&n()},e.src=i}();var t,n}t(),e.addEventListener("scroll",function(){!function(t,n){clearTimeout(t.tId),t.tId=setTimeout(function(){t.call(n)},500)}(t,e)})}(this);</script></body></html>