题目描述
有一个H行W列的网格,’.’就是能走,并且有些点上面有药品使用后能够获得一定的能量,’S’所在网格时起点,’T’时终点,每一次都能够消耗1点能量,垂直或水平的移动一个,询问是否能够走到终点。
样例
4 4
S...
#..#
#...
..#T
4
1 1 3
1 3 5
3 2 1
2 3 1
Yes
算法1
(bfs) $O(n)$
看到网格首先想到了bfs,但这道题有点奇怪的是,他并不是每一个点只经过一次,因为你走到某一个点如果你选择使用上面的药品,能量值并不是累加,而是直接变成药品提供的能量值,因此可能第一次没有使用药品走过一个点,之后再走过来补充药品。因此我们可以用贪心的策略记录到达每一个位置的最大能量值,对于第一次走到的点,如果使用药品能够让能量增多那么我们就使用药品,如果不行直接走过,不使用药品,所以o(n)的复杂度肯定是假的,但是数据范围小,影响不大
C++ 代码
#include<bits/stdc++.h>
using pii=std::pair<int,int>;
using i64=long long;
const int N=250;
bool vis[N][N];
int n,h,w,e[N][N];
int hp[N][N];
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin>>h>>w;
pii start,end;
std::vector<std::string>s(h);
for(int i=0;i<h;i++){
std::cin>>s[i];
for(int j=0;j<w;j++){
if(s[i][j]=='S'){
start={i,j};
}
if(s[i][j]=='T'){
end={i,j};
}
}
}
std::cin>>n;
for(int i=0;i<n;i++){
int r,c,w;
std::cin>>r>>c>>w;
r--,c--;
e[r][c]=w;
}
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
auto bfs=[&]()->void{
std::queue<pii>q;
q.push(start);
int stx=start.first,sty=start.second;
hp[stx][sty]=e[stx][sty];
while(q.size()){
auto t=q.front();
q.pop();
int x=t.first,y=t.second;
vis[x][y]=1;
for(int i=0;i<4;i++){
int a=x+dx[i],b=y+dy[i];
if(a<0||a>=h||b<0||b>=w||s[a][b]=='#'||hp[x][y]<=0){
continue;
}
if(!vis[a][b]){
vis[a][b]=1;
if(!e[a][b]){
hp[a][b]=hp[x][y]-1;
}
else{
if(e[a][b]>hp[x][y]-1){
hp[a][b]=e[a][b];
}
else{
hp[a][b]=hp[x][y]-1;
}
}
q.push({a,b});
}
else{
if(hp[x][y]-1>hp[a][b]){
hp[a][b]=hp[x][y]-1;
q.push({a,b});
}
}
}
}
};
bfs();
std::cout<<(vis[end.first][end.second]?"Yes\n":"No\n");
return 0;
}