比赛 EYOI与SBOI开学欢乐赛1st 评测结果 AATTTTTTTT
题目名称 拖拉机 最终得分 20
用户昵称 湖岸与夜与咸鱼 运行时间 8.000 s
代码语言 C++ 内存使用 30.85 MiB
提交时间 2022-08-29 21:05:00
显示代码纯文本
// 河南省实验中学 高中 21级 关天泽

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define re register

const int N = 0x3f3f3f;
using namespace std;

int n, x, y;
int a[2050][2050];
int b[2050][2050];
int c[50050][2];

void search(int times, int n, int m){
	b[n][m] = times;
//	cout << "x: " << n << " y: " << m << " times: " << times << " a: " << a[n][m] << endl;
	if (a[n + 1][m] == 0 && b[n + 1][m] == 0 && (n + 1) < 200 && (n + 1) >= 0) search(times, n + 1, m);
	if (a[n - 1][m] == 0 && b[n - 1][m] == 0 && (n - 1) < 200 && (n - 1) >= 0) search(times, n - 1, m);
	if (a[n][m + 1] == 0 && b[n][m + 1] == 0 && (m + 1) < 200 && (m + 1) >= 0) search(times, n, m + 1);
	if (a[n][m - 1] == 0 && b[n][m - 1] == 0 && (m - 1) < 200 && (m - 1) >= 0) search(times, n, m - 1);
}

int main(){
	freopen("tractor.in", "r", stdin);
	freopen("tractor.out", "w", stdout);
	cin >> n >> x >> y;
	for (int i = 1; i <= n;i ++){
		int q, w;
		cin >> q >> w;
		c[i][0] = q, c[i][1] = w;
		a[q][w] = 1;
//		cout << a[q][w] << " " << q << " " << w << endl;
	}
	search(1, 0, 0);
	int tm = 1;
	while (tm++){
		if (b[x][y] != 0){
			cout << b[x][y] - 1 << endl;
			return 0;
		}
//		cout << tm << endl;
		for (int i = 1; i <= n; i++){
			if(a[c[i][0]][c[i][1]] == 1){
//				cout << a[c[i][0]][c[i][1]] << " " << c[i][0] << " " << c[i][1] << endl;
				if (b[c[i][0] + 1][c[i][1]] != 0 && (c[i][0] + 1) < 200 && (c[i][0] + 1) >= 0) a[c[i][0]][c[i][1]] = 0, b[c[i][0]][c[i][1]] = tm;
				if (b[c[i][0] - 1][c[i][1]] != 0 && (c[i][0] - 1) < 200 && (c[i][0] - 1) >= 0) a[c[i][0]][c[i][1]] = 0, b[c[i][0]][c[i][1]] = tm;
				if (b[c[i][0]][c[i][1] + 1] != 0 && (c[i][1] + 1) < 200 && (c[i][1] + 1) >= 0) a[c[i][0]][c[i][1]] = 0, b[c[i][0]][c[i][1]] = tm;
				if (b[c[i][0]][c[i][1] - 1] != 0 && (c[i][1] - 1) < 200 && (c[i][1] - 1) >= 0) a[c[i][0]][c[i][1]] = 0, b[c[i][0]][c[i][1]] = tm;
//				cout << a[c[i][0]][c[i][1]] << " " << c[i][0] << " " << c[i][1] << endl;
				search(tm, c[i][0], c[i][1]);
			}
		}
	}
//	for (int i = 10; i >= 0; i--){
//		for (int j = 0; j <= 10; j++){
//			cout << b[i][j] << " ";
//		}
//		cout << endl;
//	}
	return 0;
}