洛谷 P1849 ——Tractor S

题目描述
经过一天漫长的工作，农场主 John 完全忘记了他的拖拉机还在场地中央。

他的奶牛们总喜欢和他搞些恶作剧，它们在场地的不同位置丢下 $n$ 堆干草。这样 John 就必须先移走一些干草堆才能将拖拉机开走。

拖拉机和干草堆都可以看作是二维平面上的点，它们的坐标都是整数，没有哪堆干草的坐标和拖拉机的初始坐标一致。

John 驾驶拖拉机只能沿着坐标轴的方向移动若干单位长度，比如说，他可以先朝北移动 $2$ 个单位长度，再向东移动 $3$ 个单位长度等等。

拖拉机不能移动到干草堆所占据的点。

请你帮助 John 计算一下，最少要移动多少堆干草才能将拖拉机开回坐标原点。

输入格式
第一行是三个用空格隔开的整数，依次代表干草的堆数 $n$ 和拖拉机的起始坐标 ( x 0 , y 0 ) (x_0, y_0) (x0​,y0​)

第 $2$ 行到第 $(n+1)$ 行，每行有两个用空格隔开的整数，第 $(i+1)$ 行的整数 x i , y i x_i, y_i xi​,yi​，代表第 $i$ 堆干草的坐标为 ( x i , y i ) (x_i, y_i) (xi​,yi​)

输出格式
一个整数，表示最少要移动多少堆干草 John 才能将拖拉机开回坐标原点。

输入样例
7 6 3
6 2
5 2
4 3
2 1
7 3
5 4
6 4

输出样例
1

数据范围
1 ≤ n ≤ 5 × 1 0 4 1≤n≤5×10^4 1≤n≤5×104， 1 ≤ x i , y i ≤ 1 0 3 1≤x_i,y_i≤10^3 1≤xi​,yi​≤103

题解：BFS（双端队列）

$拖拉机可以走第0行第0列，也可以走第1001行第1001列$

#include 
using namespace std;typedef pair<int, int> PII;const int N = 1010;bool g[N][N];
int n, sx, sy;
int dist[N][N];int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};void bfs()
{deque<PII> q;memset(dist, -1, sizeof dist);q.push_back({sx, sy});dist[sx][sy] = 0;while(q.size()){PII t = q.front(); q.pop_front();for (int i = 0; i < 4; i ++){int a = t.first + dx[i], b = t.second + dy[i];if(a < 0 || a >= N || b < 0 || b >= N || dist[a][b] != -1) continue;dist[a][b] = dist[t.first][t.second] + g[a][b];if(g[a][b]) q.push_back({a, b});else q.push_front({a, b});}}
}int main()
{cin >> n >> sx >> sy;while(n --){int x, y;cin >> x >> y;g[x][y] = true;}bfs();cout << dist[0][0] << endl;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！