题意

略

数据范围：$1 \le n \le 50000$

题解

优先队列$\text{bfs}$，以移动的干草堆数升序

代码：

#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define mp make_pair
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
const int N=1000+10;
int n,sx,sy,x,y;
bool m[N][N];
bool vis[N][N];
int v[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
inline int bfs(){
    priority_queue<pip,vector<pip>,greater<pip> > pq;
    pq.push(mp(0,mp(sx,sy)));
    vis[sx][sy]=1;
    for(;!pq.empty();){
        pip u=pq.top();
        pq.pop();
        int x=u.second.first,y=u.second.second;
        if(x==0 && y==0)
            return u.first;
        for(int i=0;i<4;i++){
            int nx=x+v[i][0],ny=y+v[i][1];
            if(nx<0 || nx>N || ny<0 || ny>N || vis[nx][ny])
                continue;
            vis[nx][ny]=1;
            pq.push(mp(u.first+m[nx][ny],mp(nx,ny)));
        }
    }
}
int main(){
    scanf("%d%d%d",&n,&sx,&sy);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&x,&y);
        m[x][y]=1;
    }
    printf("%d",bfs());
    return 0;
}

---

版权属于：Pelom

本文链接：https://pelom.top/archives/114/

转载时须注明出处及本声明