题目描述
解析
纯搜索，注意不能用 \(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;//dij
vs[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 go
if(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 there
if(mp[pos.fi][pos.se]==2)
for(pair<int,int> h:shou[pos.fi][pos.se])//beasts:I am here
if(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 go
if(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\) ，贪心依然成立，搜索题也可以用。
标签：tx,ty,dp,pos,tm,穿越,se From： https://www.cnblogs.com/ppllxx-9G/p/18192270