题目描述
解析
纯搜索，注意不能用 \(dfs\) ！！！
-
每次四个方向以及所有传送门，判断 \(rain\) 最早下的时间，判雨；
-
对于兽，如果醒了，等它着再走过去，需要判脚下兽，脚下雨，下一个点的雨。
code
#include<bits/stdc++.h>
#define se second
#define fi first
using namespace std;
const int N = 305;
int n,m,mp[N][N],a,b,dp[N][N],up[N][N],rain[N][N];
bool vs[N][N];
int cnt,ans=10000;
pair<int,int> csm[N*N];
vector<pair<int,int> > shou[N][N];
int xx[4]={-1,0,1,0},yy[4]={0,-1,0,1};
priority_queue<pair<int,pair<int,int> > > q; void dj()
{q.push({0,{1,1}});while(!q.empty()){pair<int,int> pos=q.top().se;int tm=dp[pos.fi][pos.se]; q.pop(); if(vs[pos.fi][pos.se]) continue;//dijvs[pos.fi][pos.se]=1;for(int i=0;i<4;i++){int tx=pos.fi+xx[i],ty=pos.se+yy[i];if(tx<=0||tx>n||ty<=0||ty>m) continue;if(rain[tx][ty]<=tm+1||mp[tx][ty]==1) continue;//rain and wall int tmp=tm;if(mp[tx][ty]==2){for(pair<int,int> j:shou[tx][ty])//beasts:I will goif(j.fi<=tm+1&&j.se>=tm+1){if(rain[pos.fi][pos.se]<=j.se||rain[tx][ty]<=j.se+1) tm=1e9;//rain:here and thereif(mp[pos.fi][pos.se]==2)for(pair<int,int> h:shou[pos.fi][pos.se])//beasts:I am hereif(h.fi<=j.se&&h.se>=j.se) tm=1e9;if(tm!=1e9) tm=max(tm,j.se);} }if(dp[tx][ty]>tm+1){dp[tx][ty]=tm+1;q.push({-dp[tx][ty],{tx,ty}});}tm=tmp;}if(mp[pos.fi][pos.se]==3)//gate{for(int i=1;i<=cnt;i++){int tx=csm[i].fi,ty=csm[i].se;if(rain[tx][ty]<=tm+2) continue;//rain:I will goif(dp[tx][ty]>tm+2){dp[tx][ty]=tm+2;q.push({-dp[tx][ty],{tx,ty}}); }} } }
}
int main()
{freopen("cross.in","r",stdin);freopen("cross.out","w",stdout);memset(dp,0x3f,sizeof(dp)); dp[1][1]=0;memset(rain,0x3f,sizeof rain);scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%d",&mp[i][j]);if(mp[i][j]==3) csm[++cnt]=make_pair(i,j);}}scanf("%d",&a);for(int i=1;i<=a;i++){int t; scanf("%d",&t);int p; scanf("%d",&p);for(int j=1;j<=p;j++){int x,y; scanf("%d%d",&x,&y);rain[x][y]=min(rain[x][y],t);}}scanf("%d",&b);for(int i=1;i<=b;i++){int t1,t2; scanf("%d%d",&t1,&t2);int x,y; scanf("%d%d",&x,&y);shou[x][y].push_back(make_pair(t1,t2));}dj();printf("%d\n",dp[n][m]);return 0;
}
注意
码力有待提升，赛时唐氏 \(dfs\) ，数据再水也得 \(\mathbb{T}\) 。
注意 \(dij\) 就是优先队列优化的 \(bfs\) ，贪心依然成立，搜索题也可以用。
