P5099 [USACO04OPEN] Cave Cows 4https://www.luogu.com.cn/problem/P5099

思路：

这里的垫蹄石之间很明显是有后效性的 所以不能用dp来做

考虑宽搜

我们每次都枚举和这个垫蹄石之间x方向和z方向的距离均不超过2的垫脚石

因为都很大 我们可以使用

代码：

#include<bits/stdc++.h>
#define PI pair<int,int>
using namespace std;
int n,m,a[51000],b[51000];
map<PI,bool>mp;
map<PI,bool>vis;
queue<PI>q;
queue<int>p;
int BFS()
{q.push({0,0});p.push(0);while(!q.empty()){PI x=q.front();q.pop();int y=p.front();p.pop();//printf("%d %d %d\n",x.first,x.second,y);for(int i=-2;i<=2;i++){for(int j=-2;j<=2;j++){int xx=x.first+i;int yy=x.second+j;if(mp.count({xx,yy})&&vis.count({xx,yy})==0){if(yy==m){return y+1;}vis[{xx,yy}]=1;q.push({xx,yy});p.push(y+1);}}}}return -1;
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){int x,y;scanf("%d%d",&x,&y);mp[{x,y}]=1;}printf("%d",BFS());return 0;
}