文字教学

这道题是带状态的BFS问题，因为除了位置 (x,y)，血量 hp 也是关键状态（同一位置不同血量是不同情况，需分别记录）：

1. 状态定义：用 vis[x][y][h] 记录“在位置 (x,y) 且血量为 h”的状态是否已访问，避免重复搜索。
2. BFS队列元素：存储当前位置 (x,y)、当前血量 hp、已走步数 step。
3. 移动规则：每走一步血量减1，必须保证减后血量 >0（否则死亡）；若走到鼠标格（4），血量补满到6。
4. 终止条件：走到家（3）时直接返回当前步数+1；队列空仍未到家返回-1。

代码

#include <bits/stdc++.h>
using namespace std;

int g[10][10], vis[10][10][7];
int n, m, sx, sy;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct Node {
    int x, y, hp, step;
};

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> g[i][j];
            if (g[i][j] == 2) {
                sx = i;
                sy = j;
            }
        }
    }
    queue<Node> q;
    q.push({sx, sy, 6, 0});
    vis[sx][sy][6] = 1;
    while (!q.empty()) {
        Node cur = q.front();
        q.pop();
        for (int d = 0; d < 4; ++d) {
            int nx = cur.x + dx[d];
            int ny = cur.y + dy[d];
            int nhp = cur.hp - 1;
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (g[nx][ny] == 0) continue;
            if (nhp <= 0) continue;
            if (g[nx][ny] == 4) nhp = 6;
            if (vis[nx][ny][nhp]) continue;
            vis[nx][ny][nhp] = 1;
            if (g[nx][ny] == 3) {
                cout << cur.step + 1 << endl;
                return 0;
            }
            q.push({nx, ny, nhp, cur.step + 1});
        }
    }
    cout << -1 << endl;
    return 0;
}