【题目描述】
干了一整天的活，农夫约翰完全忘记了他把拖拉机落在田地中央了。
他的奶牛非常调皮，决定对约翰来场恶作剧。
她们在田地的不同地方放了 $N$ 捆干草，这样一来，约翰想要开走拖拉机就必须先移除一些干草捆。
拖拉机的位置以及 $N$ 捆干草的位置都是二维平面上的整数坐标点。
拖拉机的初始位置上没有干草捆。
当约翰驾驶拖拉机时，他只能沿平行于坐标轴的方向（北，南，东和西）移动拖拉机，并且拖拉机必须每次移动整数距离。
例如，驾驶拖拉机先向北移动 $2$ 单位长度，然后向东移动$3$单位长度。
拖拉机无法移动到干草捆占据的位置。
请帮助约翰确定他需要移除的干草捆的最小数量，以便他能够将拖拉机开到二维平面的原点。
【输入格式】
第一行包含三个整数：$N$以及拖拉机的初始位置$(x,y)$。
接下来 $N$ 行，每行包含一个干草捆的位置坐标 $(x,y)$。
【输出格式】
输出约翰需要移除的干草捆的最小数量。
【数据范围】
$1≤N≤50000$
$1≤x,y≤1000$
解题思路
不知道这是不是我做的第一个双端队列广搜，可能以前做过，但是这个题让我很是眼前一亮。
这个题我一开始想的就是，从起点开始广搜BFS，然后遇到原点就退出，但是这里不是求最短路，也许路最短，但是要移走更多的草垛，所以这种方法不可取，但是可以用这个双端队列广搜的方法可以做到。
还写一下，题目的转化，我们通过花费来一步步转化到图论的题目，看起来原来的二维确实一个图论题。
我们这个双端队列广搜，实际上就是一个Dijkstra，简直一模一样，可以对照代码来看、
双端队列广搜
一改往常的queue，我们采用的是deque，我们在最先将草垛为权值1，这里点权和边权都可以，实际上二者就是一样的东西。
如上图，我们遇到一个点，如果它是0，也就是没有草垛，那么就没有权值，放入队列前端；如果它是1，这说明我们需要花费1，这时候我们需要放到后面去。这样为什么？这样能保证我们的花费最小，花费最小也就是草垛最小。
可能这时候有点晕了，没有的话为什么放前面就可以？这样就是贪心嘛，不需要草垛的话就放前面就好，那假如一直都插入前面呢？这说明没有草垛我们也可以一步步走完所有的点最后走到原点。
还有一个重要的性质，如图右下角所示，在一个双向队列中，权值只可能相差一。为什么呢？因为我们每次最多加1放到后面，当前面所有不加1或者之前进队的pop完毕之后，才会选取后半段继续完成操作。
写到这里，双端队列广搜就很容易理解了吧。
inline void Case_Test()
{
cin>>n>>sx>>sy;
for (int i=1;i<=n;i++)
{
cin>>x>>y;
a[x][y]=1;
}
Q.push_back({sx,sy});
memset(dis,0x3f,sizeof(dis));
dis[sx][sy]=0;
while (!Q.empty())
{
auto t=Q.front();Q.pop_front();
x=t.first;y=t.second;
if (vis[x][y]) continue;
vis[x][y]=1;//Dij的优化思想就是在于每个点只走一次
if (x==0&&y==0) break;//原点break
for (int i=0;i<4;i++)
{
int tx=x+dx[i],ty=y+dy[i];//偏移量
if (tx>=0&&tx<=MAXN&&ty>=0&&ty<=MAXN)//判断是否可以走，不用管上界，多走几步也可以的
{
int w=a[tx][ty];//看权值，点权
if (dis[tx][ty]>dis[x][y]+w)//和dij很像，如果可以更新的话，那就入队
{
dis[tx][ty]=dis[x][y]+w;
if (w) Q.push_back({tx,ty});
else Q.push_front({tx,ty});
}
}
}
}
cout<<dis[0][0];
}
文章评论