比赛 |
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;
}