我有一个非常复杂的做法:
先对每个有药的点 bfs 这个点的能量那么多层。处理出每个有药的点能到哪些有药的点。
然后 Floyd 求一个传递闭包。
最后看从起点能到哪些有药的点,再从那些点扩展,看能否到终点。
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
int X[305],Y[305],E[305],id[205][205],a[205][205],dx[5]={0,-1,0,1,0},dy[5]={0,0,-1,0,1},n,m,T,sx,sy,ex,ey;
bool vis[205][205],mat[205][205],f[305][305];
struct node{
int x,y,d;
};
void bfs(int x,int y,int k){
queue<node>q;
q.push((node){x,y,0});
vis[x][y]=true;
while(!q.empty()){
int x=q.front().x,y=q.front().y,d=q.front().d;
q.pop();
if(d==k) continue;
for(int i=1;i<=4;i++){
int xx=x+dx[i],yy=y+dy[i];
if(mat[xx][yy]==0&&xx>=1&&xx<=n&&yy>=1&&yy<=m&&vis[xx][yy]==false){
vis[xx][yy]=true;
q.push((node){xx,yy,d+1});
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
string s;
cin>>s;
for(int j=0;j<m;j++){
if(s[j]=='S'){
sx=i;
sy=j+1;
}
if(s[j]=='T'){
ex=i;
ey=j+1;
}
if(s[j]=='#') mat[i][j+1]=1;
}
}
cin>>T;
int pos=0;
for(int i=1;i<=T;i++){
cin>>X[i]>>Y[i]>>E[i];
if(X[i]==sx&&Y[i]==sy) pos=i;
}
if(!pos){
if(sx==ex&&sy==ey) cout<<"Yes";
else cout<<"No";
return 0;
}
for(int i=1;i<=T;i++){
memset(vis,0,sizeof(vis));
bfs(X[i],Y[i],E[i]);
for(int j=1;j<=T;j++)
if(vis[X[j]][Y[j]]) f[i][j]=1;
}
for(int i=1;i<=T;i++) f[i][i]=1;
for(int k=1;k<=T;k++)
for(int i=1;i<=T;i++)
for(int j=1;j<=T;j++)
f[i][j]|=(f[i][k]&f[k][j]);
for(int i=1;i<=T;i++){
if(f[pos][i]){
memset(vis,0,sizeof(vis));
bfs(X[i],Y[i],E[i]);
if(vis[ex][ey]){
cout<<"Yes";
return 0;
}
}
}
cout<<"No";
return 0;
}
by aCssen @ 2024-04-06 22:30:53
@[aCssen](/user/534296) 大师我悟了
by tianyu_awa @ 2024-04-06 22:37:40
@[aCssen](/user/534296) o,thx
by HeYilin @ 2024-04-07 22:29:08