题解 P5099 【[USACO2004OPEN]Cave Cows 4 洞穴里的牛之四】

· · 题解

简单 bfs

直接枚举两个点判断能否连边，复杂度 n^2 ，不可行

发现每个石头能够到达的点有限，只有自己周围的几个格子，于是用 map 存每一个格子中有哪块石头，枚举自己周围的石头进行连边后 bfs 即可

因为 map 很慢，你可能需要 O2

#include <bits/stdc++.h>
#define Fast_cin ios::sync_with_stdio(false), cin.tie();
#define rep(i, a, b) for(register int i = a; i <= b; i++)
#define per(i, a, b) for(register int i = a; i >= b; i--)
#define DEBUG(x) cerr << "DEBUG" << x << " >>> " << endl;
using namespace std;

typedef unsigned long long ull;
typedef long long ll;

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') fu = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

const int N = 5e4 + 5, INF = 0x7fffffff;

map <pair <int, int>, int> pre;
queue <int> q;
vector <int> adj[N];
int x[N], y[N], dis[N];
int n, t, m;

int main() {
    read(t); read(m); while(t--) {
        int a, b; read(a); read(b);
        pair <int, int> t = make_pair(a, b);
        if(pre.count(t)) continue;
        x[++n] = a; y[n] = b; pre[t] = n;
    }
    n++; x[n] = 0; y[n] = 0; pre[make_pair(0, 0)] = n;
    for(register int i = 1; i <= n; i++) {
        for(register int t1 = -2; t1 <= 2; t1++) {
            for(register int t2 = -2; t2 <= 2; t2++) {
                if(!t1 && !t2) continue;
                int _x = x[i] + t1, _y = y[i] + t2;
                if(pre.count(make_pair(_x, _y))) {
                    adj[i].push_back(pre[make_pair(_x, _y)]);
                }
            }
        }
    }
    memset(dis, -1, sizeof(dis)); dis[n] = 0; q.push(n);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(register int i = 0; i < (int)adj[u].size(); i++) {
            int v = adj[u][i];
            if(dis[v] == -1) {
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
    }
    int ans = INF;
    for(register int i = 1; i < n; i++) {
        if(y[i] == m && ~dis[i]) {
            ans = min(ans, dis[i]);
        }
    }
    if(ans == INF) ans = -1;
    print(ans, '\n');
    return 0;
}