题解 P2802 【回家】
题目传送门 P2802
首先最短路一开始想到的是dijkstra或者bfs。
而这题由于会回满血的缘故，dijkstra较为难描述
当然，咱都是搜索dfs进来的
分析这道题可注意到以下几点：
- 障碍物、边界外是肯定不走的，这在模拟每步之前就要排除滴
- 除去障碍物、边界外，在小H还没到达家时，你看看，无论我从哪走开，我都要扣血1（这是重点！一定要注意，题目是说，离开一个空地才扣血，不是到达空地！意思就是说，我在模拟每一次走到下一个格子之前，我的血量一定要大于1！不然我走到下一个格子，我的血量就是0，无论我的下一个格子是家还是鼠标，小H已经死了！！！不能安全到家或回满血！）
- 众所周知，dfs通常有一个数组来标记是否走过这个点，当然，这里也需要用vis数组来记录下了，但是这里并不只是标记走没走过，下面会讲！（你想想，如果不标记的话，那我不是可以在有鼠标的一小范围内转圈？题目还有说，这个格子的鼠标捡完是还有的哦。死循环不是。）那这里到底怎么标记呢？如果像往常一样，标记的不走，合理么？
比如这组数据：
0 0 0 4 0 0 0
0 0 0 1 0 0 0
3 1 1 ① 1 1 2
注意打圈的①那个点，我虽然直线从2走到3正好是没血的，不能到家，但是我可以走到①然后往上走，回满血，之后再从①出口，往家走，这样步数为10。然而我们发现，我们不能标记每一格只走一次，所以在这里，我们的vis应该是步数限制而不是 走过了就不走！我试了一下，最多可以设置到，每个格子至多走22次，多了会超时或栈溢出MLE
接下来就在代码里了~
#include<bits/stdc++.h>
#define MAXN 10
#define inf 0x3f3f3f3f
using namespace std;
int a[MAXN][MAXN], vis[MAXN][MAXN];
int n, m, sx, sy, fx, fy;// (sx,sy)为起点坐标，(fx,fy)为终点坐标，当然n，m是行和列
int sum;//用来统计最少步数的，一开始要初始化为最大(如上面预处理inf）
int to[][2] = { {0,1},{0,-1},{-1,0},{1,0} };//模拟4个方向
void dfs(int u, int v,int ans,int t)//(u,v)代表当前小H所在坐标，ans记录当前的血量，t记录到目前为止已耗费的时间
{
if (u == fx && v == fy)//到家啦~
{
sum = min(sum, t);//保留最小步数
return;
}
if (t >= sum)//这个if是后加的，是为了剪枝（之前没加也过了。。）当然，如果都模拟到这一步了，小H还没到达终点时，t就已经比之前的一种到达家的路径所耗费时间更多了，这条路就不再下去了
return;
if (ans > 1)//这是之前所说的，我在模拟每一步之前，我的血量一定要大于1，不然就返回了（返回相当于这段的dfs没执行了，因为if外边下面啥没有= =）
{
for (int i = 0; i < 4; i++)//模拟出上下左右走
{
int q = u + to[i][0], w = v + to[i][1];//模拟走一格之后的坐标
if (q >= 0 && q < n&&w >= 0 && w < m && vis[q][w]<=22 && a[q][w] != 0)//走到这个格子时，我不能超边界&&限制每个格子所走的步数&&不能是大板墙~
{
vis[q][w] ++;//走过的次数+1
if (a[q][w] == 4)
{
dfs(q, w, 6, t + 1);//如果我走到了4了，当然我就回满血了~~ 并且步数+1
}
else
{
dfs(q, w, ans - 1, t + 1);//否则我走到这只是扣血，步数也要+1
}
vis[q][w] --;//减少这个格子的次数，消除影响
}
}
}
}
int main()
{
cin >> n >> m;
sum = inf;//初始化
memset(vis, 0, sizeof(vis));//初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
if (a[i][j] == 2)
sx = i, sy = j;//找出起点坐标
else if (a[i][j] == 3)
fx = i, fy = j;//找出家坐标
}
}
dfs(sx, sy, 6, 0);//从起点开始，血量为6，步数为0。开始深搜
if (sum == inf)//如果sum没有被更新，那就说明没有达到家
cout << "-1" << endl;
else
cout << sum << endl;//否则输出这个最短时间
}祝各位以及忙碌的审核人新年快乐~