Loading... 干了一整天的活,农夫约翰完全忘记了他把拖拉机落在田地中央了。 <!--more--> 他的奶牛非常调皮,决定对约翰来场恶作剧。 她们在田地的不同地方放了 $N$ 捆干草,这样一来,约翰想要开走拖拉机就必须先移除一些干草捆。 拖拉机的位置以及 $N$ 捆干草的位置都是二维平面上的整数坐标点。 拖拉机的初始位置上没有干草捆。 当约翰驾驶拖拉机时,他只能沿平行于坐标轴的方向(北,南,东和西)移动拖拉机,并且拖拉机必须每次移动整数距离。 例如,驾驶拖拉机先向北移动 $2$ 单位长度,然后向东移动 $3$ 单位长度。 拖拉机无法移动到干草捆占据的位置。 请帮助约翰确定他需要移除的干草捆的最小数量,以便他能够将拖拉机开到二维平面的原点。 ## 输入格式 第一行包含三个整数:$N$ 以及拖拉机的初始位置 $(x,y)$。 接下来 $N$ 行,每行包含一个干草捆的位置坐标 $(x,y)$。 ## 输出格式 输出约翰需要移除的干草捆的最小数量。 ## 数据范围 $1\leq N \leq 50000$ $1\leq x,y \leq 1000$ ## 输入样例 ```txt 7 6 3 6 2 5 2 4 3 2 1 7 3 5 4 6 4 ``` ## 输出样例 ```txt 1 ``` ## 思路 01BFS模板,使用双端队列进行维护,在往队列中放点的时候,遇到权重为0的放到队列的前端,遇到权重为1的放到队列末端。 每次从队列前端取点,当更新到$(0,0)$点时返回结果。 ## 代码 ```cpp #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define ms(a,b) memset(a,b,sizeof(a)) const int inf=0x3f3f3f3f; const ll INF=0x3f3f3f3f3f3f3f3f; const int maxn=1e6+10; const int mod=1e9+7; const int maxm=1e3+10; using namespace std; typedef pair<int,int> pii; int edge[maxm][maxm]; int num[maxm][maxm]; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; int bfs(int x,int y) { deque<pii>que; ms(num,inf); que.push_front({x,y}); num[x][y]=0; while(!que.empty()) { pii tmp=que.front(); que.pop_front(); if(!tmp.first&&!tmp.second) return num[0][0]; for(int i=0;i<4;i++) { int dx=tmp.first+dir[i][0],dy=tmp.second+dir[i][1]; if(dx<0||dx>1001||dy<0||dy>1001) continue; if(num[dx][dy]<=num[tmp.first][tmp.second]+edge[dx][dy]) continue; num[dx][dy]=num[tmp.first][tmp.second]+edge[dx][dy]; if(!edge[dx][dy]) que.push_front({dx,dy}); else que.push_back({dx,dy}); } } return -1; } int main(int argc, char const *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); srand((unsigned int)time(NULL)); #endif ios::sync_with_stdio(false); cin.tie(0); int n,x,y; cin>>n>>x>>y; int a,b; for(int i=0;i<n;i++) { cin>>a>>b; edge[a][b]=1; } cout<<bfs(x,y)<<endl; #ifndef ONLINE_JUDGE cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<" s."<<endl; #endif return 0; } ``` Last modification:January 5, 2022 © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏