P1374 题解

· · 题解

随机到一篇绿题搜索，还能写题解，当然是切掉啦。

本题看着是中等模拟加搜索的四不像题。我们将它分成四部分。

运动方式

首先，我们理解他们三人是咋运动的。萨尔和魔王的移动都是有规律可循，给你一个运动规律，模拟出这两人的运动方式。

其次是小 A 的运动。这个人比较烦，没规律可循，我们就需要使用 BFS 搜索小 A 的移动。

搜索

搜索我们需要在结构体中定义 8 个变量来存储移动信息，不愧是绿题的搜索，没那么简单。分别是 xa,ya,xs,ys,xm,ym,s,t。分别对应小 A 的坐标，萨尔的坐标，魔王的坐标，当前时间，离开光环的时间。

接下来就是搜索的主要部分。第一步，我们需要模拟萨尔和魔王的移动。顺便判断一下有没有相遇。

w=q.front();
xa=w.xa,ya=w.ya;
xs=w.xs,ys=w.ys;
xm=w.xm,ym=w.ym;
s=w.s,t=w.t;
int nx,ny;
nx=xs+fx[a[s%a.size()]-48],ny=ys+fy[a[s%a.size()]-48];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&v[nx][ny]==0) xs=nx,ys=ny;
nx=xm+fx[b[s%b.size()]-48],ny=ym+fy[b[s%b.size()]-48];
if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&v[nx][ny]==0) xm=nx,ym=ny;
//模拟萨尔和魔王的行动，符合要求才能移动，否则不移动。
s++;
if(xa==xm&&ya==ym) return s;

其次，枚举小 A 的行动。我们需要判断有没有超出距离，有没有超出光环的保护时间。

for(int i=1;i<=4;i++)
{
  nx=xa+fx[i],ny=ya+fy[i];
  if(nx<1||nx>n||ny<1||ny>m||v[nx][ny]||vis[nx][ny]) continue;
  double dis=sqrt((nx-xs)*(nx-xs)+(ny-ys)*(ny-ys));//计算小A和萨尔的距离
  int t1=t; 
  if(dis>d) t1++;
  else t1=0;
  //重新计算保护时间
  if(t1<=s1)
  {
    if(nx==xm&&ny==ym) return s;//必须特判！否则喜提70pts
    vis[nx][ny]=1;
    q.push(data{nx,ny,xs,ys,xm,ym,s,t1});
    //符合要求，加入新节点
  }
}
q.pop();

细节处理

  1. 搜索小 A 的行动时特判两人有没有相遇，否则会喜提 70pts。

  2. 记得将结构体出队。

  3. 操作中定义新变量操作，否则变量不清空导致爆零。

  4. 一开始记得将起点设置为已访问。

我们就轻松过了一道绿题。