【正经题解】回家

我们使用做题的三个步骤来完成这道题目：

1.读题
题目给出了一个地图，地图上有空地、障碍物、出发点、家和带有鼠标的格子，小H只能沿着封锁线上的空地移动，每移动一格消耗1点血量，血量降到0即被淘汰，可以通过拾取鼠标来补满血量，但如果血量降到0才拾取鼠标无效，不能到达家即使在家门口淘汰也不能算完成任务。

2.思路
使用宽度优先搜索（𝐵𝐹𝑆）算法求解最短时间。从小H的出发点开始，不断向四个方向扩展，更新血量和步数，并标记已访问的位置。当到达家时，返回步数。如果无法到达家，则返回-1。

3.代码
主函数包含了输入输出部分，bfs函数实现了𝐵𝐹𝑆算法的具体逻辑，结构体𝑁𝑜𝑑𝑒定义了每个点的属性。

#include <iostream>
#include <queue>
using namespace std;

// 定义一个结构体Node表示每个点的坐标、血量和步数
struct Node {
    int x;      // x坐标
    int y;      // y坐标
    int hp;     // 血量
    int steps;  // 步数
};

// 定义一个函数bfs，使用BFS算法求解最短时间
int bfs(int n, int m, int map[][100]) {
    // 定义一个bool数组vis来记录访问过的点的坐标和血量
    bool vis[100][100][7] = {0};
    // 定义一个队列q，用于BFS遍历
    queue<Node> q;
    int tX, tY;
    // 找到小H的出发点的坐标
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (map[i][j] == 2) {
                tX = i;
                tY = j;
                break;
            }
        }
    }
    // 将出发点加入队列
    q.push({tX, tY, 6, 0});
    // 标记出发点已访问
    vis[tX][tY][6] = true;
    // 定义两个数组表示坐标的变化量
    int dx[] = {0, 0, 1, -1};
    int dy[] = {1, -1, 0, 0};
    // 开始BFS
    while (!q.empty()) {
        Node p = q.front(); // 取出队首元素
        q.pop();            // 弹出队首元素
        // 如果当前点是家的位置，返回步数
        if (map[p.x][p.y] == 3) {
            return p.steps;
        }
        // 遍历四个方向
        for (int i = 0; i < 4; ++i) {
            int nx = p.x + dx[i]; // 计算新的x坐标
            int ny = p.y + dy[i]; // 计算新的y坐标
            // 判断是否在地图范围内且不是障碍物
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && map[nx][ny] != 0) {
                int new_hp = p.hp - 1;      // 更新血量
                int new_steps = p.steps + 1;// 更新步数
                // 如果当前格子有鼠标，则血量回满
                if (map[nx][ny] == 4)
                    new_hp = 6;
                // 如果血量大于0且未访问过该点，则加入队列
                if (new_hp > 0 && !vis[nx][ny][new_hp]) {
                    q.push({nx, ny, new_hp, new_steps}); // 将新的点加入队列
                    vis[nx][ny][new_hp] = true;          // 标记为已访问
                }
            }
        }
    }
    return -1; // 无法到达家
}

// 主函数
int main() {
    int n, m;
    cin >> n >> m;
    int map[100][100];
    // 读取地图
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> map[i][j];
        }
    }
    // 调用bfs函数求解最短时间
    int time = bfs(n, m, map);
    // 输出结果
    cout << time << endl;
    return 0;
}