题目链接：小红勇闯地下城

#include <bits/stdc++.h>
#define int long long //将所有的int替换成long long 防止爆
using namespace std;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
void dijkstra(int n, int m, int u, int v, vector<string> &mp, vector< vector<int> > &d, vector< vector<bool> > &st) // 对地图跑dijkstra算法 
{
    priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> q; // 存储三个变量的优先队列 
    q.push({0, u, v}); 
    // 第一个表示(u, v)到当前位置的当前最短距离为 0 
    // 第二个和第三个变量表示当前位置的行和列
    // 从(u, v)开始遍历地图 
    st[u][v] = true; // 将(u, v)标记为已来过 
    d[u][v] = 0; // (u, v)到(u, v)的最短距离为 0 
    while(q.size()) // 如果优先队列不为空 
    {
        auto [dis, x, y] = q.top(); // 取出队头 
        q.pop(); // 弹出队头 
        for(int i = 0; i < 4; i++) // 移动 
        {
            int tx = x + dx[i], ty = y + dy[i]; // 移动后的位置 
            if(tx >= 0 && tx < n && ty >= 0 && ty < m && !st[tx][ty]) // 移动后的位置没来过且合法 
            {
                st[tx][ty] = true; // 将移动后的位置标记为已来过 
                d[tx][ty] = min(d[tx][ty], d[x][y] + (mp[tx][ty] - '0')); // 更新最短距离 
                q.push({d[tx][ty], tx, ty}); // 加入优先队列 
            }
        }
    }
}
void solve()
{
	int q;
    cin >> q;
    while(q--)
    {
        int n, m, h;
        cin >> n >> m >> h;
        vector<string> mp(n); // 存储地图 
        vector< vector<int> > d(n, vector<int>(m, INF)); // 记录从(u, v)到(i, j)的最短距离 
        vector< vector<bool> > st(n, vector<bool>(m, false)); // 标记当前位置有没有来过 
        for(int i = 0; i < n; i++) // 读入地图 
            cin >> mp[i];
        int u, v, x, y;
        for(int i = 0; i < n; i++) // 找到起点和终点 
        {
            for(int j = 0; j < m; j++)
            {
                if(mp[i][j] == 'S') // S 为起点 
                {
                    u = i;
                    v = j;
                    mp[i][j] = '0'; // 起点没有怪，故此处为 0 
                }
                if(mp[i][j] == 'T') // T 为终点 
                {
                    x = i;
                    y = j;
                    mp[i][j] = '0'; // 终点没有怪，故此处为 0 
                }
            }
        }
        dijkstra(n, m, u, v, mp, d, st); // 跑一遍最短路 
        // 如果最低血量消耗 大于等于 已有血量，则无法安全到达终点 
        if(d[x][y] >= h) cout << "No" << endl;
        else cout << "Yes" << endl;
    }
}
signed main()
{
	int T = 1;
//	cin >> T; // 根据具体情况注释 
	while(T--)
		solve();
	return 0;
}

这个C++代码主要实现了一个简化的Dijkstra算法，用于在给定地图上找到从起点（'S'）到终点（'T'）的最短路径。地图上的每个位置都有一个对应的权值（表示为怪物数量或0），并且起点和终点的权值被设置为0。算法的目的是确定玩家是否能够从起点到达终点，同时保证玩家剩余的生命值（由输入给出）不少于0。

以下是代码的详细分析：

头文件和宏定义

  • #include <bits/stdc++.h>：包含了C++标准库的大部分头文件。
  • #define int long long：将int类型重定义为long long，以避免整数溢出。
  • using namespace std;：使用标准命名空间。

常量和全局变量

  • const int N = 1e6 + 10, INF = 0x3f3f3f3f;：定义了常量N（一个较大的数）和INF（表示“无穷大”的距离）。
  • int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};：用于表示四个方向的移动。

函数：dijkstra

  • 这个函数实现了Dijkstra算法。
  • 它使用一个优先队列（最小堆）来存储待处理的节点和它们到起点的距离。
  • st数组用于标记已访问过的节点。
  • d数组用于存储从起点到每个节点的最短距离。

函数：solve

功能

solve函数处理单个查询，该查询包含一个地图、玩家的起始位置'S'、目标位置'T'以及玩家的初始生命值。函数的目的是判断玩家是否能够从起点到达终点，同时保证剩余生命值非负。

输入

  • 地图的尺寸（n行m列）
  • 玩家的初始生命值h
  • 描述地图的字符串数组mp

处理流程

  1. 初始化：

    • 创建一个二维数组d来存储从起点到地图上每个位置的最短距离（即最小怪物数量）。初始时，除起点外，所有位置的距离都设置为无穷大（INF）。
    • 创建一个二维布尔数组st来标记地图上哪些位置已经被访问过。初始时，所有位置都标记为未访问。
    • 遍历地图，找到起点S和终点T，并将它们在地图上的表示（'S'和'T'）替换为'0'，因为起点和终点没有怪物。

  2. 执行Dijkstra算法：

    • 调用dijkstra函数，传入地图尺寸、起点和终点的坐标、地图数组、最短距离数组d以及访问状态数组st。
    • dijkstra函数会更新d数组，使其包含从起点到每个可达位置的最短距离。

  3. 结果判断：

    • 检查从起点到终点的最短距离（即路径上怪物数量的总和）是否小于或等于玩家的初始生命值h。
    • 如果是，则输出"Yes"，表示玩家可以安全到达终点。
    • 否则，输出"No"，表示玩家无法安全到达终点。

输出

  • 字符串"Yes"或"No"，表示玩家是否能够安全到达终点。

主函数：main

  • 主函数根据需要处理的测试用例数量调用solve函数。
  • 在这个例子中，T被硬编码为1，但也可以通过输入来设置。