小红勇闯地下城时间限制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^51051 ≤ h ≤ 10 9 1≤h≤10^91≤h≤109输出描述对于每次询问输出一行答案如果小红能安全到达终点则输出 Y e s YesYes。否则输出 N o NoNo。示例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 hh则存活。关键操作定位起点终点、SPFA 维护最小累计伤害、四方向网格遍历。效率保障队列优化的广度优先搜索无冗余计算完美处理题目大数据范围。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n,m,h;cinnmh;ll sx,sy,ex,ey;vectorstringv(n);for(ll i0;in;i){cinv[i];for(ll j0;jm;j){if(v[i][j]S){sxi;syj;}if(v[i][j]T){exi;eyj;}}}vectorvectorlld(n,vectorll(m,h));queuepairll,llq;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 i0;i4;i){ll nxxdx[i];ll nyydy[i];if(nx0nxnny0nym){if(nxexnyey){coutYes\n;return;}if(nxsxnysy)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});}}}}coutNo\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cint;while(t--)solve();return0;}
小红勇闯地下城【牛客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^51051 ≤ h ≤ 10 9 1≤h≤10^91≤h≤109输出描述对于每次询问输出一行答案如果小红能安全到达终点则输出 Y e s YesYes。否则输出 N o NoNo。示例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 hh则存活。关键操作定位起点终点、SPFA 维护最小累计伤害、四方向网格遍历。效率保障队列优化的广度优先搜索无冗余计算完美处理题目大数据范围。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidsolve(){ll n,m,h;cinnmh;ll sx,sy,ex,ey;vectorstringv(n);for(ll i0;in;i){cinv[i];for(ll j0;jm;j){if(v[i][j]S){sxi;syj;}if(v[i][j]T){exi;eyj;}}}vectorvectorlld(n,vectorll(m,h));queuepairll,llq;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 i0;i4;i){ll nxxdx[i];ll nyydy[i];if(nx0nxnny0nym){if(nxexnyey){coutYes\n;return;}if(nxsxnysy)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});}}}}coutNo\n;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);ll t;cint;while(t--)solve();return0;}
