概述
Rescue
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 36678 Accepted Submission(s): 12701
URL
http://acm.hdu.edu.cn/showproblem.php?pid=1242
Introduction
迷宫题，上下左右移动，每次移动消耗 1 单位时间，'.' 是路，'#' 是墙，唯一的 'a' 是起点，任意一个 'r' 是终点，'x' 代表守卫，经过守卫格会额外消耗 1 单位时间。输入迷宫矩阵，若能自起点到达终点则输出最短耗时，否则输出扑街。
Input
多组，读至EOF。每组第一行是两个整数 R C，代表行数、列数，接下来 R 行是 R 个长度为 C 的字符串（不含空格的字符串），代表整个迷宫矩阵。（矩阵字符含义详见上文 Introduction ）
Output
若能自起点到达终点则输出最短耗时带回车，否则输出 "Poor ANGEL has to stay in the prison all his life." 。
Sample Input
7 8
#.#####.
#.a#..r.
#..#x..
..#..#.#
#...##..
.#......
........
Sample Output
13
Analysis & AC code
本题是经典的迷宫搜索题，DFS 与 BFS 都可解决本题，但由于本题最短时的特点 ，BFS 的速度将优于 DFS。
由于起点唯一，而终点可能有多个，故只可从起点开始搜索。
下面对 DFS 和 BFS 分别进行分析。
DFS：
- 暴力搜索，需要寻找所有可能的路径，并更新最短时
- 1. 初始化：vis数组清0
- 2. 搜索至终点时：更新最短时（全局变量）
- 3. 剪枝：if 当前时间 >= 当前最短时，进行剪枝
- 4. 回溯：使用 “vis标记1 --> 递归 --> vis标记0” 进行回溯搜索
以下是DFS代码：
/** HDU 1242 DFS迷宫
* by Kevin.
*/
#include <cstdio>
#include <cstring>
#define M 223
#define visit(x) vis[x.r][x.c]=1
#define notVis(x) !vis[x.r][x.c]
#define valid(x) x.r>=0&&x.c>=0&&x.r<R&&x.c<C&&a[x.r][x.c]!='#'
using namespace std;
char a[M][M];
char vis[M][M];
int R, C, r1, c1, minTime;
const int dr[] = {-1,1,0,0};
const int dc[] = {0,0,-1,1};
void DFS(int r, int c, int time)
{
if(a[r][c]=='r')
{
if(time<minTime)
minTime = time;
return;
}
if(time>=minTime)
return;
int rr, cc, i, ntime;
for(i=0; i<4; i++)
{
rr = r+dr[i];
cc = c+dc[i];
if(a[rr][cc]!='#' && !vis[rr][cc] && rr>=0 && rr<R && cc>=0 && cc<C)
{
if(a[rr][cc]=='x')
ntime = time+2;
else
ntime = time+1;
char temp = a[rr][cc];
vis[rr][cc] = 1;
DFS(rr, cc, ntime);
vis[rr][cc] = 0; // 回溯
}
}
}
int main()
{
int r, c;
while(scanf("%d %d",&R,&C)!=EOF)
{
memset(vis, 0, sizeof(vis));
minTime = 0xFFFF;
for(r=0; r<R; r++)
{
for(c=0; c<C; c++)
{
scanf(" %c",a[r]+c);
if(a[r][c] == 'a')
r1 = r, c1 = c;
}
}
vis[r1][c1] = 1;
DFS(r1, c1, 0);
if(minTime!=0xFFFF)
printf("%dn",minTime);
else
puts("Poor ANGEL has to stay in the prison all his life.");
}
return 0;
}
BFS：
- 普通队列实现的BFS：
- 1. 初始化：
- vis数组清0，head tail 队列指针置 0
- 标记 vis 起点为1
- 起点入队
- 2. 对出队结点的操作：
- 如果为终点，则说明找到了最短时路径，结束搜索
- 如果为守卫点，则将此点更改为普通路径点，并将耗时++，然后再次入队（此次入队可不必再次标记 vis），代表进行了一次战斗
-
注意：此题非常特殊，因为 战斗时间 == 移动时间，故仍可使用普通队列进行BFS。但如果是 != 则只能选用优先队列，否则将会打乱队列内部严格的时间增序！
- 如果为普通路径点或起点，则试探邻接的四个点，若未访问过且不为墙结点，则访问之并将耗时++，然后入队。
- 1. 初始化：
以下是使用普通队列的BFS代码：
/** HDU 1242 BFS迷宫 普通队列实现
* by Kevin.
*/
#include <cstdio>
#include <cstring>
#define M 223
#define visit(x) vis[x.r][x.c]=1
#define notVis(x) !vis[x.r][x.c]
#define valid(p) p.r>=0&&p.c>=0&&p.r<R&&p.c<C&&a[p.r][p.c]!='#'
using namespace std;
struct Point
{
int r, c, time;
Point(void) { }
Point(int rr, int cc) : r(rr), c(cc) { }
};
Point q[10*M], src;
char a[M][M];
char vis[M][M];
int R, C, minTime;
const int dr[] = {-1,1,0,0};
const int dc[] = {0,0,-1,1};
bool BFS()
{
bool out = false;
Point now, next;
int head = 0, tail = 0;
visit(src);
q[tail++] = src;
while(head!=tail)
{
now = q[head++];
switch(a[now.r][now.c])
{
case'r':
out = true;
minTime = now.time;
break;
case'x':
++now.time;
a[now.r][now.c] = '.';
q[tail++] = now; // 此次入队可不必再次标记 vis
break;
default:
++now.time;
for(int i=0; i<4; ++i)
{
next = now;
next.r += dr[i];
next.c += dc[i];
if(valid(next) && notVis(next))
{
visit(next);
q[tail++] = next;
}
}
break;
}
if(out)
break;
}
return out;
}
int main()
{
int r, c;
while(~scanf("%d %d", &R, &C))
{
memset(vis, 0, sizeof(vis));
for(r=0; r<R; r++)
{
for(c=0; c<C; c++)
{
scanf(" %c",a[r]+c);
if(a[r][c] == 'a')
src.r = r, src.c = c;
}
}
src.time = 0;
if(BFS())
printf("%dn", minTime);
else
puts("Poor ANGEL has to stay in the prison all his life.");
}
return 0;
}
- 优先队列实现的BFS：
【CGWR】在 HDU 本题的 discuss 区有很多小伙伴反映自己的优先队列 BFS 怎么也过不去，在分析了他们的代码之后，博主发现此题有一个 巨坑 ，下面进行分析
- 首先是【错误示例】：
- 1. 初始化：
- vis数组清0
- 标记 vis 起点为1
- 起点入队
- 2. 对出队结点的操作：
- 如果为终点，则说明找到了最短时路径，结束搜索
- 如果为普通路径点或起点，则试探邻接的四个点，若未访问过且不为墙结点，则访问之并将耗时++，然后入队。
- 如果为守卫点，也试探上下左右四个点，若未访问过且不为墙结点，则访问之并将耗时 +=2，然后入队。
- 1. 初始化：
我们把普通队列实现的 BFS 代码中的 case 'x' 进行修改，便得到以下【错误示例代码】
/** HDU 1242 BFS迷宫错误示例 优先队列实现
* by Kevin.
*/
#include <cstdio>
#include <cstring>
#include <queue>
#define M 223
#define visit(x) vis[x.r][x.c]=1
#define notVis(x) !vis[x.r][x.c]
#define valid(p) p.r>=0&&p.c>=0&&p.r<R&&p.c<C&&a[p.r][p.c]!='#'
using namespace std;
struct Point
{
int r, c, time;
Point(void) { }
Point(int rr, int cc) : r(rr), c(cc) { }
inline bool operator < (const Point &ot) const
{
return time > ot.time;
}
};
Point src;
char a[M][M];
char vis[M][M];
int R, C, minTime;
const int dr[] = {-1,1,0,0};
const int dc[] = {0,0,-1,1};
bool BFS()
{
bool out = false;
priority_queue<Point> pq;
Point now, next;
visit(src);
pq.push(src);
while(!pq.empty())
{
now = pq.top();pq.pop();
switch(a[now.r][now.c])
{
case'r':
out = true;
minTime = now.time;
break;
case'x': // 此处进行修改
now.time+=2;
for(int i=0; i<4; ++i)
{
next = now;
next.r += dr[i];
next.c += dc[i];
if(valid(next) && notVis(next))
{
visit(next);
pq.push(next);
}
}
break;
default:
++now.time;
for(int i=0; i<4; ++i)
{
next = now;
next.r += dr[i];
next.c += dc[i];
if(valid(next) && notVis(next))
{
visit(next);
pq.push(next);
}
}
break;
}
if(out)
break;
}
return out;
}
int main()
{
int r, c;
while(~scanf("%d %d", &R, &C))
{
memset(vis, 0, sizeof(vis));
for(r=0; r<R; r++)
{
for(c=0; c<C; c++)
{
scanf(" %c",a[r]+c);
if(a[r][c] == 'a')
src.r = r, src.c = c;
}
}
src.time = 0;
if(BFS())
printf("%dn", minTime);
else
puts("Poor ANGEL has to stay in the prison all his life.");
}
return 0;
}为什么会错呢？这里 错就错在 ：此代码是在向上下左右扩展结点之前，就根据当前点是否为守卫点决定此次扩展后新入队结点的 time 是 += 1 还是 += 2。而正确的做法是 ：在向上下左右扩展结点的过程中，根据当前点的扩展点是否为守卫点决定此次扩展后新入队结点的 time 是 += 1 还是 += 2。
一言以蔽之，就是 time += 2 应该发生在即将扩展至守卫点时，而不是守卫点出队后。
例：
x r
a .
显然答案应该是 2 ，然而按照上面的【错误示例代码】却输出了3
为什么 r 的 time 会更新为 3 呢？我们来看一下到底发生了什么：
- 首先 a 入队，a 的 time 是 0
- 然后 a 出队，按照【上、下、左、右】的顺序，将 x 和 . 入队，由于在这份代码中 time += 2 发生在守卫点出队后，因此它们的 time 都是 1 （因为当前出队的是 a ）
- 然后 x 出队，按照【上、下、左、右】的顺序，将 r 入队，由于在这份代码中 time += 2 发生在守卫点出队后，因此 r 的 time 是 3 （因为当前出队的是 x ）
- 然后 . 出队，由于 r 已经被访问且时间已经被设定为 3，故此时无法再使 r 重新入队，尽管现在产生的 r 的 time 更小
正是由于 time += 2 的发生时间 不正确，导致优先队列没有发挥出 “ 优先 ” 的作用。
解决方法有二：
- 1. 不修改time += 2 的发生时间，将 vis 数组更改为 int 类型，仍初始化为0，其某点的值设定为到此点的最小 time。如果 time 不为 0 的话就入队，否则将当前 time 与已有 time 进行比较，如果更小则更新最小值。
- 2. 修改time += 2 的发生时间 为 即将扩展至守卫点时，这样优先队列仍然能发挥出 “ 优先 ” 的作用。
下面贴出 方法 2 的 AC代码：
/** HDU 1242 BFS迷宫AC代码 优先队列实现
* by Kevin.
*/
#include <cstdio>
#include <cstring>
#include <queue>
#define M 223
#define visit(x) vis[x.r][x.c]=1
#define notVis(x) !vis[x.r][x.c]
#define valid(x) x.r>=0&&x.c>=0&&x.r<R&&x.c<C&&a[x.r][x.c]!='#'
using namespace std;
struct Point
{
int r, c, time;
Point(void) { }
Point(int rr, int cc) : r(rr), c(cc) { }
inline bool operator < (const Point &ot) const
{
return time > ot.time;
}
};
Point src;
char a[M][M];
char vis[M][M];
int R, C, minTime;
const int dr[] = {-1,1,0,0};
const int dc[] = {0,0,-1,1};
bool BFS()
{
priority_queue<Point> pq;
Point now, next;
src.time = 0;
visit(src);
pq.push(src);
while(!pq.empty())
{
now = pq.top();pq.pop();
for(int i=0; i<4; ++i)
{
next.time = now.time+1;
next.r = now.r + dr[i];
next.c = now.c + dc[i];
if(valid(next) && notVis(next))
{
visit(next);
switch(a[next.r][next.c])
{
case'r':
minTime = next.time;
return true;
case'x':
++next.time;
pq.push(next);
break;
default:
pq.push(next);
break;
}
}
}
}
return false;
}
int main()
{
int r, c;
while(~scanf("%d %d", &R, &C))
{
memset(vis, 0, sizeof(vis));
for(r=0; r<R; r++)
{
for(c=0; c<C; c++)
{
scanf(" %c",a[r]+c);
if(a[r][c] == 'a')
src.r = r, src.c = c;
}
}
src.time = 0;
if(BFS())
printf("%dn", minTime);
else
puts("Poor ANGEL has to stay in the prison all his life.");
}
return 0;
}
最后
以上就是无辜小松鼠为你收集整理的【HDU 1242】搜索 | DFS | BFS | 迷宫 | CGWR | N Rescue注意：此题非常特殊，因为 战斗时间 == 移动时间，故仍可使用普通队列进行BFS。但如果是 != 则只能选用优先队列，否则将会打乱队列内部严格的时间增序！的全部内容，希望文章能够帮你解决【HDU 1242】搜索 | DFS | BFS | 迷宫 | CGWR | N Rescue注意：此题非常特殊，因为 战斗时间 == 移动时间，故仍可使用普通队列进行BFS。但如果是 != 则只能选用优先队列，否则将会打乱队列内部严格的时间增序！所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复