比赛 |
EYOI与SBOI开学欢乐赛1st |
评测结果 |
AWAAAAAWWW |
题目名称 |
拖拉机 |
最终得分 |
60 |
用户昵称 |
yrtiop |
运行时间 |
1.276 s |
代码语言 |
C++ |
内存使用 |
10.55 MiB |
提交时间 |
2022-08-29 20:17:44 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
#define fir first
#define sec second
#define mp make_pair
const int maxn = 5e4 + 5;
const int INF = 0x3f3f3f3f;
const int maxm = 1e3 + 5;
bool v[maxm][maxm];
std::deque<std::pair<int,int> > q;
int n,s,t,d[maxm][maxm],fx[] = {0 , 1 , 0 , -1},fy[] = {1 , 0 , -1 , 0};
int main() {
freopen("tractor.in","r",stdin);
freopen("tractor.out","w",stdout);
scanf("%d %d %d",&n,&s,&t);
for(int i = 1;i <= n;++ i) {
int x,y;
scanf("%d %d",&x,&y);
v[x][y] = true;
}
memset(d , 0x3f , sizeof(d));
q.push_back(mp(s , t));
d[s][t] = 0;
while(!q.empty()) {
int x = q.front().fir,y = q.front().sec;
q.pop_front();
for(int k = 0;k < 4;++ k) {
int nx = fx[k] + x,ny = fy[k] + y;
if(nx < 1||nx > 1000||ny < 1||ny > 1000)continue ;
if(d[nx][ny] ^ INF)continue ;
d[nx][ny] = d[x][y] + v[nx][ny];
if(v[nx][ny])q.push_front(mp(nx , ny));
else q.push_back(mp(nx , ny));
}
}
int ans = INF;
for(int i = 1;i <= 1000;++ i) {
ans = std::min(ans , std::min(d[1][i] , std::min(d[i][1] , std::min(d[1000][i] , d[i][1000]))));
}
printf("%d\n",ans);
return 0;
}