acwing2019.拖拉机（双端队列广搜）

干了一整天的活，农夫约翰完全忘记了他把拖拉机落在田地中央了。
他的奶牛非常调皮，决定对约翰来场恶作剧。
她们在田地的不同地方放了 NN 捆干草，这样一来，约翰想要开走拖拉机就必须先移除一些干草捆。
拖拉机的位置以及 NN 捆干草的位置都是二维平面上的整数坐标点。
拖拉机的初始位置上没有干草捆。
当约翰驾驶拖拉机时，他只能沿平行于坐标轴的方向（北，南，东和西）移动拖拉机，并且拖拉机必须每次移动整数距离。
例如，驾驶拖拉机先向北移动 22 单位长度，然后向东移动 33 单位长度。
拖拉机无法移动到干草捆占据的位置。
请帮助约翰确定他需要移除的干草捆的最小数量，以便他能够将拖拉机开到二维平面的原点。

输入格式

第一行包含三个整数：NN 以及拖拉机的初始位置 (x,y)(x,y)。
接下来 NN 行，每行包含一个干草捆的位置坐标 (x,y)(x,y)。

输出格式

输出约翰需要移除的干草捆的最小数量。

数据范围

1≤N≤500001≤N≤50000,
1≤x,y≤10001≤x,y≤1000

输入样例：

7 6 3 6 2 5 2 4 3 2 1 7 3 5 4 6 4

输出样例：

1

//能走出界
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N = 1010;
int dist[N][N];
bool st[N][N],g[N][N];      //st判重，g记录干草
int dx[4] = {-1,0,1,0}, dy[4] = {0,1,0,-1};
int bfs(int sx, int sy) {
    deque<PII> q;
    q.push_front({sx,sy});
    memset(dist,0x3f,sizeof dist);
    dist[sx][sy] = 0;
    while (q.size()) {
        auto t = q.front();
        q.pop_front();
        //判重
        if (st[t.x][t.y]) continue;
        st[t.x][t.y] = true;
        //剪枝
        if (!t.x && !t.y) break;
        for (int i = 0; i < 4; ++i) {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a >= 0 && a < N && b >= 0 && b < N) {
                int w = 0;
                if (g[a][b]) w = 1;
                if (dist[a][b] > dist[t.x][t.y] + w) {
                    dist[a][b] = dist[t.x][t.y] + w;
                    //加入队列
                    if (!w) q.push_front({a,b});
                    else q.push_back({a,b});
                }
            }
        }
    }
    return dist[0][0];
}
int main() {
    int n,sx,sy;
    scanf("%d%d%d",&n,&sx,&sy);
    while (n -- ) {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x][y] = true;
    }
    cout << bfs(sx,sy) << endl;
    return 0;
}