回家(Going Home) 题解

思路分析

使用广度优先搜索（BFS）。由于同一个格子可能需要在吃过鼠标补满血后以更高血量再次经过，不能用普通布尔 vis[r][c]，而应记录到达每个格子时的历史最高血量 maxHp[r][c]：从状态 (r, c, hp, dist) 扩展一步后剩余血量为 nhp = hp - 1；若 nhp == 0 则当场死亡（即使目标格是家 3 或鼠标 4 也无效）；否则若目标格是 3 直接返回 dist + 1，若目标格是 4 则令 nhp = 6，当且仅当 nhp > maxHp[nr][nc] 时更新并入队。

参考代码

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

struct Node
{
    int r, c, hp, dist;
};

int g[12][12];
int maxHp[12][12];
const int DR[4] = {-1, 1, 0, 0};
const int DC[4] = {0, 0, -1, 1};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    int sr = 0, sc = 0;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cin >> g[i][j];
            if (g[i][j] == 2) { sr = i; sc = j; }
        }
    }
    queue<Node> q;
    maxHp[sr][sc] = 6;
    q.push({sr, sc, 6, 0});
    while (!q.empty())
    {
        Node cur = q.front();
        q.pop();
        if (cur.hp <= 1) continue;
        for (int d = 0; d < 4; ++d)
        {
            int nr = cur.r + DR[d], nc = cur.c + DC[d];
            if (nr < 0 || nr >= n || nc < 0 || nc >= m || g[nr][nc] == 0) continue;
            if (g[nr][nc] == 3)
            {
                cout << cur.dist + 1 << "\n";
                return 0;
            }
            int nhp = (g[nr][nc] == 4) ? 6 : (cur.hp - 1);
            if (nhp > maxHp[nr][nc])
            {
                maxHp[nr][nc] = nhp;
                q.push({nr, nc, nhp, cur.dist + 1});
            }
        }
    }
    cout << -1 << "\n";
    return 0;
}