2019. 拖拉机
- 题目
- 提交记录
- 讨论
- 题解
- 视频讲解
干了一整天的活，农夫约翰完全忘记了他把拖拉机落在田地中央了。
他的奶牛非常调皮，决定对约翰来场恶作剧。
她们在田地的不同地方放了 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
范围应该是0-1001，使用广度优先进行图的搜索，因为有草堆和空地，使用双端队列，草地和空地都入队，但是优先选择空旷地，所以空地存储在front，草地在back
#include<iostream>
#include<algorithm>
#include<vector>
#include<deque>
#include<cstring>
using namespace std;
#define x first//pair成员定义
#define y second//pair成员定义
const int N=1010;
int g[N][N],cao[N][N];//g存储有不空地
typedef pair<int,int>pii;
deque<pii>d;
int sx,sy,n,x,y;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
int bfs(int sx,int sy){
memset(cao,0x3f,sizeof(cao));
d.push_back({sx,sy});
cao[sx][sy]=0;
while(d.size()){
pii p=d.front();
d.pop_front();
if(p.x==0&&p.y==0)return cao[0][0];
for(int i=0;i<4;i++){
int a=p.x+dx[i],b=p.y+dy[i];
if(a<0||a>1001||b<0||b>1001)continue;//超限时
if(cao[a][b]<=cao[p.x][p.y]+g[a][b])continue;//当前草堆数量小于时，不需要更新
cao[a][b]=cao[p.x][p.y]+g[a][b];
if(g[a][b])d.push_back({a,b});//有草堆
else d.push_front({a,b});//无草堆
}
}
return -1;
}
int main(){
cin>>n>>sx>>sy;
for(int i=1;i<=n;i++){
cin>>x>>y;
g[x][y]=1;
}
cout<<bfs(sx,sy);
return 0;
}