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