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;
}