比赛 EYOI与SBOI开学欢乐赛1st 评测结果 AAAAAAAAAA
题目名称 拖拉机 最终得分 100
用户昵称 lihaoze 运行时间 0.447 s
代码语言 C++ 内存使用 6.61 MiB
提交时间 2022-08-29 19:58:47
显示代码纯文本
#include <bits/stdc++.h>

struct P { int x, y, cnt; };

const int N = 50010, M = 1010;
P a[N];
bool g[M][M], st[M][M];
int n, ans = 1e9, mx, my;
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };

bool valid(int x, int y) {
	return x >= 1 && x <= mx && y >= 1 && y <= my;
}

void bfs() {
	std::queue<P> q;
	q.push(a[0]);
	while (q.size()) {
		P now = q.front(); q.pop();
		for (int i = 0; i < 4; ++ i) {
			int x = now.x + dx[i],
			    y = now.y + dy[i],
			    cnt = now.cnt;
			if (!valid(x, y))
				ans = std::min(ans, cnt);
			else if (g[x][y] && !st[x][y] && cnt + 1 < ans)
				q.push((P){x, y, cnt + 1}),
				st[x][y] = true;
			else if (!g[x][y] && !st[x][y] && cnt < ans)
				q.push((P){x, y, cnt}),
				st[x][y] = true;
		}
	}
}

int main() {
	freopen("tractor.in", "r", stdin);
	freopen("tractor.out", "w", stdout);
	std::cin >> n >> a[0].x >> a[0].y, a[0].cnt = 0;
	for (int i = 1; i <= n; ++ i) {
		int x, y; std::cin >> x >> y;
		mx = std::max(mx, x);
		my = std::max(my, y);
		g[x][y] = true;
	}
	bfs();
	std::cout << ans << '\n';
	return 0;
}