F:水题!!!!!!
这题就是有抽象条件、行动限制、规模不大的图上的最短路搜索。
直接去模拟一定会 ,因为有些位置可能会有多个状态相同或不同的水滴经过,会导致有些位置无意义的重复搜索。
所以重点是对状态的去重,我们可以借鉴 算法的去重方式,建立一个
表示在位置
已经有方向为
的水滴经过过。
我们直接去写模拟结合 (重点是去重),然后就写完了。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=1e3+10;
int n,m,h;
int mp[N][N];
bool st[N][N][5];
struct water{
int x, y, d, t;
bool operator<(const water &p) const { return t<p.t; };
bool operator>(const water &p) const { return t>p.t; };
};
int main(){
cin.tie(0)->sync_with_stdio(false);
cout.tie(0);
cin>>n>>m>>h;
int bx,by,ex,ey;
string s;
for(int i=1;i<=n;i++){
cin>>s;
for(int j=1;j<=m;j++){
mp[i][j]=0;
if(s[j-1]=='*') bx=i, by=j;
if(s[j-1]=='%') ex=i, ey=j;
if(s[j-1]=='#') mp[i][j]=1e9;
}
}
priority_queue<water,vector<water>,greater<water>> heap;
heap.push({bx,by,1,0});
while(!heap.empty()){
auto [x,y,d,t]=heap.top();
heap.pop();
if(x==ex&&y==ey){
cout<<t;
return 0;
}
if(st[x][y][d])continue;
st[x][y][d]=true;
if(d==1){
int tx=x+1,ty=y;
if(tx>n) continue;
if(t>=mp[tx][ty]) heap.push({tx,ty,1,t+1});
else{
heap.push({tx,ty,1,t+h+1});
mp[tx][ty]=t+h+1;
if(y-1>0&&mp[x][y-1]<=t) heap.push({x,y-1,2,t+1});
if(y+1<=m&&mp[x][y+1]<=t) heap.push({x,y+1,3,t+1});
}
}
if(d==2){
if(x+1<=n){
if(mp[x+1][y]<=t) heap.push({x+1,y,1,t+1});
else if(y-1>0&&mp[x][y-1]<=t) heap.push({x,y-1,2,t+1});
}
}
if(d==3){
if(x+1<=n){
if(mp[x+1][y]<=t) heap.push({x+1,y,1,t+1});
else if(mp[x][y+1]<=t) heap.push({x,y+1,3,t+1});
}
}
}
cout<<-1;
}