小红勇闯地下城【牛客tracker 每日一题】
小红勇闯地下城
时间限制：1秒 空间限制：256M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
小红被传送到了一个地下城，地下城有n nn行m mm列的，共n ∗ m n∗mn∗m个房间。其中有一些房间有怪物。
小红初始有h hh血量，当她遭遇到一个战斗力为x xx的怪物时，她会消耗x xx的血量然后击杀这个怪物。小红想知道，自己能否找到一条路径成功安全到达终点？
我们认为，如果小红到达终点时的血量为正，则安全到达终点。血量小于等于0 00时死亡。
小红在迷宫中只能上下左右移动到相邻房间。
输入描述：
第一行输入一个正整数q qq，代表询问次数。
接下来共有q qq次询问：
每次询问，首先第一行输入三个正整数n , m , h n,m,hn,m,h，代表迷宫的行数、列数，以及小红初始的血量。
接下来的n nn行，每行输入一个长度为m mm的字符串。字符串仅包含数字字符（′ 0 ′ ˜ ′ 9 ′ '0' \~\ '9'′0′˜′9′）、′ S ′ 'S'′S′和′ T ′ 'T'′T′。其中数字代表房间里怪物的血量（′ 0 ′ '0'′0′代表该房间没有怪物），′ S ′ 'S'′S′代表小红的起点，′ T ′ 'T'′T′代表小红的终点。
我们默认，起点和终点是没有怪物的。
保证所有询问n ∗ m n∗mn∗m的和不超过10 5 10^5105
1 ≤ h ≤ 10 9 1≤h≤10^91≤h≤109
输出描述：
对于每次询问输出一行答案：
如果小红能安全到达终点，则输出" Y e s " "Yes""Yes"。否则输出" N o " "No""No"。
示例1
输入：
2 3 3 3 S01 292 20T 2 2 1 4S 6T输出：
No Yes说明：
第一组询问，小红显然无法到达终点。
第二组询问，虽然小红初始只有1 11血量，但直接往下即可不遭遇怪物到达终点。
解题思路
本题核心是最短路径求解（SPFA），目标是找到从起点到终点总伤害最小的路径。小红存活的条件是路径总伤害严格小于初始血量h hh，因此只需计算最小总伤害即可判断结果。首先遍历迷宫定位起点S SS和终点T TT，用二维数组维护到达每个格子的最小累计伤害，初始时起点伤害为0。通过队列进行四方向扩展，若移动到新格子的总伤害更小，则更新数值并加入队列。遍历过程中若抵达终点，直接判定可行；若队列为空仍未到达终点，则判定不可行。算法时间复杂度适配总网格数≤ 10 5 ≤10^5≤105的约束，高效稳定。
总结
核心逻辑：将问题转化为求起点到终点的最小伤害路径，最小伤害< h < h<h则存活。
关键操作：定位起点终点、SPFA 维护最小累计伤害、四方向网格遍历。
效率保障：队列优化的广度优先搜索，无冗余计算，完美处理题目大数据范围。
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;voidsolve(){ll n,m,h;cin>>n>>m>>h;ll sx,sy,ex,ey;vector<string>v(n);for(ll i=0;i<n;i++){cin>>v[i];for(ll j=0;j<m;j++){if(v[i][j]=='S'){sx=i;sy=j;}if(v[i][j]=='T'){ex=i;ey=j;}}}vector<vector<ll>>d(n,vector<ll>(m,h));queue<pair<ll,ll>>q;q.push({sx,sy});d[sx][sy]=0;ll dx[4]={1,-1,0,0};ll dy[4]={0,0,1,-1};while(!q.empty()){auto[x,y]=q.front();q.pop();for(ll i=0;i<4;i++){ll nx=x+dx[i];ll ny=y+dy[i];if(nx>=0&&nx<n&&ny>=0&&ny<m){if(nx==ex&&ny==ey){cout<<"Yes"<<'\n';return;}if(nx==sx&&ny==sy)continue;if(d[x][y]+(v[nx][ny]-'0')>=h)continue;if(d[x][y]+(v[nx][ny]-'0')<d[nx][ny]){d[nx][ny]=d[x][y]+(v[nx][ny]-'0');q.push({nx,ny});}}}}cout<<"No"<<'\n';}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cin>>t;while(t--)solve();return0;}