P2802 回家 题解
BurningEnderDragon
·
·
题解
题目链接：P2802 回家
引言
显然，这是一道迷宫类的题目，而解决迷宫类题目最常用的算法是广度优先搜索（Breadth First Search，简称 BFS）。
如果你还不知道什么是 BFS，可以参考这道题目，以及我的题解。
当然，这道题也有使用深度优先搜索（Depth First Search，简称 DFS）的解法。一定程度上，DFS 解决迷宫问题会比 BFS 麻烦，如果你想尝试，可以参考其他人的题解，在此不再赘述。
细节
若小 H 在鼠标或家所在的格子上 HP 刚好降为 0，小 H 也会死去。如下面这组数据：
1 7
2 0 0 0 0 0 3
小 H 无法安全到家。
所以当小 H 的 PH 为 1 时，我们即可判定小 H 已经死亡，因为他无论下一步走到何种格子上都会直接死去。
解法
在传统的迷宫问题中，每个格子最多只能被搜索一次，所以可以使用一个 bool 型的 visited[] 数组来记录每个格子是否被访问过。
而在本题中，稍加思考就会发现，因为捡鼠标可以补充 HP，所以可能会出现最优解需要多次经过同一个格子的情况，例如下面这组数据：
6 6
2 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0
1 1 4 0 0 0
1 0 0 0 0 0
1 4 1 1 1 3
作图如下：
令 (i,j) 表示第 i 行第 j 列的格子，则图中：
小 H 回家的路径如下图的红色箭头所示：
显然，在这组数据中，存在且仅存在这一种回家的路径，因为如果小 H 不捡 (4,3) 的鼠标，他将在 (6,2) 刚好死去。
即在某些情况中，若不重复经过一些格子，根本无法到达终点。
在这个路径中，(4,1) 和 (4,2) 都被经过了两次。
本题的突破点在于：在何种情况下，一个格子可以被重复经过？
答案是本次经过这个格子时剩余的 HP 都大于（不是大于或等于）之前经过时剩余的 HP 时。
因为多次经过一个格子时，步数必定比之前经过时大，所以若当前状态比之前的状态更优，则必定 HP 更高。因此上述结论成立。
仍用上面这组数据举例：
$(4,2)$ 在第一次被经过时，步数为 $4$，HP 为 $2$，而第二次被经过时步数为 $6$，HP 为 $5$。
所以把传统 BFS 中的 `visited[]` 数组改为 `int` 类型，用于**记录经过这个格子时最大的 HP** 即可，
当尝试扩展一个空地时，若发现当前 HP 大于之前的最大 HP，即可成功扩展。
**而有鼠标的格子最多只能被经过一次，因为每次经过这个格子时，HP 都会补满。**
## 代码
完整 AC 代码如下：
其中 `exit()` 函数用于直接结束程序，函数参数为 $0$ 时表示程序正常结束，可在输出最终答案后免去函数返回的麻烦，它包含在 `<cstdlib>` 头文件中。
```cpp
#include <cstdio>
#include <cstdlib>
#include <queue>
using std::queue;
struct Place //用结构体存储经过一个格子时的状态：当前格子的横纵坐标、步数以及 HP
{
int x,y,step,HP;
};
int n,m;
int square[10][10]={}; //格子的种类
int visited[10][10]={}; //经过一个格子时的最大 HP
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
queue<Place> que; //广度优先搜索需要的队列
void BFS() //广度优先搜索
{
while(!que.empty())
{
int x=que.front().x,y=que.front().y,step=que.front().step,HP=que.front().HP;
que.pop();
if(square[x][y]==3)
{
printf("%d\n",step); //第一次扩展到家所在的格子，直接输出当前步数并结束程序
exit(0);
}
if(HP>1) //HP 小于或等于 1 则判定死亡
{
for(int i=0;i<=3;++i)
{
int nx=x+dx[i],ny=y+dy[i];
if(nx>=1 && nx<=n && ny>=1 && ny<=m) //确保尝试扩展的格子坐标在合法范围内
{
if(square[nx][ny]==1 || square[nx][ny]==3) //尝试扩展的格子是空地或小 H 的家
{
if(visited[nx][ny]<HP-1) //本次经过这个格子时的 HP 小于之前经过时的最大 HP
{
visited[nx][ny]=HP-1;
que.push(Place{nx,ny,step+1,HP-1}); //步数增加 1，HP 减少 1
}
}
if(square[nx][ny]==4) //尝试扩展的格子有鼠标
{
if(!visited[nx][ny]) //有鼠标的格子最多只能被经过一次
{
visited[nx][ny]=1;
que.push(Place{nx,ny,step+1,6}); //步数增加 1，HP 补满
}
}
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
scanf("%d",&square[i][j]);
if(square[i][j]==2)
{
que.push(Place{i,j,0,6}); //将出发点入队
}
}
}
BFS();
puts("-1"); //搜索结束后仍没有到家，判定无解
return 0;
}
```