题目传送门
题目大意：
给定一个 \(n \times m\) 的地图，要求从起点 S 走到终点 T，每移动 \(1\) 个会消耗 \(1\) 点能量，障碍 # 不能走，空地为.可以走，体力消耗至 \(0\) 也无法移动，地图位置 \((x_i,y_i)\) 有一瓶可以变成 \(e_i\) 体力的药，可以选择是否喝。
问能否抵达终点，可以输出 Yes，否则输出 No。
数据范围：\(1 \leq n,m \leq 200,1 \leq x_i \leq n,1 \leq y_i \leq m,1 \leq e_i \leq n \times m\)。
题目分析：
（一眼 bfs 板题，结果赛时用了标记是否走过+优先队列的假做法 WA 了 3 个点没调出来）
这题需要判断，因为吃药这个性质特殊，是变成对应的体力值 \(e\)，而不是增加体力值 \(e\)，存在后效性，不能使用标记是否走过+优先队列，所以需要开一个 ma[][] 数组记录走到某点的最大能量，当 \(w_{x,y}>ma_{x,y}\) 才继续搜索，切记每走到有药的地方直接先让 \(w_{x,y} \gets \max(w_{x,y},a_{x,y})\)，再判断即可（a 数组存图）。
时间复杂度：\(O(nm)\)，含有较大常数。
Code：
#include<bits/stdc++.h>
using namespace std;
const int N=205;
const int dx[4]={0,0,1,-1};
const int dy[4]={1,-1,0,0};//遍历方向
int n,m,k,bx,by,ex,ey,a[N][N],ma[N][N];
//(bx,by)为起点，(ex,ey)为终点，a[][]存图，障碍为 -1，自然数能走，正整数表示有药，ma[i][j]存走到(i,j)的最大能量
struct dat//自从打过 CF 的题结构体就再也不敢命名为 data
{int x,y,w;
};//结构体存走到(x,y)有 w 能量
void bfs(int x,int y)
{queue <dat> q;//开普通队列即可q.push((dat){x,y,a[x][y]});ma[x][y]=a[x][y];while(!q.empty()){dat now=q.front();q.pop();for(int i=0;i<4;i++){int xx=now.x+dx[i];int yy=now.y+dy[i];int ww=now.w-1;if(xx==ex&&yy==ey)//是否抵达终点{printf("Yes");exit(0);//结束程序}ww=max(ww,a[xx][yy]);//走到 (xx,yy) 的最大能量if(xx<1||xx>n||yy<1||yy>m||a[xx][yy]==-1||ww<=ma[xx][yy]||ww<=0) continue;//判断越界、障碍、能量，若当前能量不超过最大能量也要停止下传q.push((dat){xx,yy,ww});ma[xx][yy]=ww;//更新走到 (xx,yy) 的最大能量}}
}
signed main()
{cin>>n>>m;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){char ch;cin>>ch;if(ch=='S') bx=i,by=j;//起点if(ch=='T') ex=i,ey=j;//终点if(ch=='#') a[i][j]=-1;//障碍}cin>>k;for(int i=1;i<=k;i++){int x,y,w;cin>>x>>y>>w;a[x][y]=w;//标记(x,y)有可以变成 w体力药 }if(!a[bx][by])//若初始位置没有能量，无法行动，不用进入 bfs，直接输出 -1{printf("No");return 0;}bfs(bx,by);printf("No");return 0;
}
