栈与队列专题详解之拖拉机

题目描述拖拉机干了一整天的活农夫约翰完全忘记了他把拖拉机落在田地中央了。他的奶牛非常调皮决定对约翰来场恶作剧。她们在田地的不同地方放了 N 捆干草这样一来约翰想要开走拖拉机就必须先移除一些干草捆。拖拉机的位置以及 N 捆干草的位置都是二维平面上的整数坐标点。拖拉机的初始位置上没有干草捆。当约翰驾驶拖拉机时他只能沿平行于坐标轴的方向 北南东和西 移动拖拉机并且拖拉机必须每次移动整数距离。例如驾驶拖拉机先向北移动 2 单位长度然后向东移动 3 单位长度。拖拉机无法移动到干草捆占据的位置。请帮助约翰确定他需要移除的干草捆的最小数量以便他能够将拖拉机开到二维平面的原点。输入格式 第一行包含三个整数N 以及拖拉机的初始位置 ( x , y ) 。接下 N 行每行包含一个干草捆的位置坐标 ( x , y ) 。输出格式 输出约翰需要移除的干草捆的最小数量。数据范围 1 ≤ N ≤ 500001 ≤ x , y ≤ 1000输入样例7 6 3 6 2 5 2 4 3 2 1 7 3 5 4 6 4输出样例1还有一种比较特殊的队列称为双端队列在入队或出队操作时的位置可以是队头也可以是队尾经常和 BFS 结合起来解决一些常见的算法问题。#includebits/stdc.h using namespace std; bool vis[1010][1010]; int G[1010][1010]; int x,y,sx,sy,n; int dir[4][2]{{1,0},{0,1},{-1,0},{0,-1}}; int res,tx,ty; int dist[1010][1010]; struct node{ int x; int y; int dis; }; dequenodeQ; node t; int main(){ scanf(%d%d%d,n,sx,sy); resn; while(n--){ scanf(%d%d,x,y); G[x][y]1; } node S; S.xsx,S.ysy,S.dis0; Q.push_back(S); vis[sx][sy]1; while(!Q.empty()){ node hQ.front(); Q.pop_front(); if(h.x0h.y0){ printf(%d,h.dis); return 0; } for(int i0;i4;i){ txh.xdir[i][0]; tyh.ydir[i][1]; if(tx0||tx1005||ty0||ty1005||vis[tx][ty]) continue; vis[tx][ty]1; t.xtx,t.yty; if(G[tx][ty]){ t.dish.dis1; Q.push_back(t); } else{ t.dish.dis; Q.push_front(t); } } }如果栈 / 队列的数满足一定的单调性则叫做单调栈 / 单调队列。在处理某些算法问题时还可能需要用到单调性例如面试中常常遇到的滑动窗口求最大 / 最小值问题。使用单调栈 / 单调队列需要时刻保证其中所有数的单调性一旦不满足单调性就要执行弹出操作。