hdu 4885 TIANKENG’s travel(bfs)

全栈程序员-站长 • 2021年12月6日下午1:00 • 未分类 • 阅读 36

大家好，又见面了，我是全栈君，祝每个程序员都可以多学几门语言。

题目大意：给定N，L，表示有N个加油站，每次加满油能够移动距离L，必须走直线，可是能够为斜线。然后给出sx，sy，ex，ey，以及N个加油站的位置，问说最少经过几个加油站，路过不加油也算。

解题思路：一開始以为经过能够不算，所以o(n2)的复杂度建图，然后用bfs求最短距离，结果被FST了。
将点依照x坐标排序，这样在建图是保证当前点为最左点，每次建立一条边的时候，将该边的斜率记录，下次有同样的斜率则不加边，斜率能够用两个整数表示，可是要注意化简成最简。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1005;

struct point {
    int id;
    ll x, y;
}p[maxn], s, e;

ll L;
int N, d[maxn];
vector<int> g[maxn];
set<pii> vis;

inline ll gcd (ll a, ll b) {
    return b == 0 ? a : gcd(b, a%b);
}

inline bool cmp (const point& a, const point& b) {
    return a.x < b.x;
}

inline ll dis (ll x, ll y) {
    return x * x + y * y;
}

bool search (ll x, ll y) {
    ll d = gcd(x, y);
    if (d < 0)
        d = -d;

    x /= d; y /= d;
    if (vis.find(make_pair(x, y)) != vis.end())
        return true;

    vis.insert(make_pair(x, y));
    return false;
}

void addEdge (point a, point b) {
    ll d = dis(a.x - b.x, a.y - b.y);
    if (d <= L && !search(b.x - a.x, b.y - a.y)) {
        g[a.id].push_back(b.id);
        g[b.id].push_back(a.id);
        //printf("%d %d %lld %lld\n", a.id, b.id, d, L * L);
    }
}

void init () {
    scanf("%d%lld", &N, &L);
    scanf("%lld%lld%lld%lld", &p[0].x, &p[0].y, &p[1].x, &p[1].y);
    p[0].id = 0;
    p[1].id = 1;

    N += 2;
    L = L * L;

    for (int i = 0; i < N; i++)
        g[i].clear();

    for (int i = 2; i < N; i++) {
        scanf("%lld%lld", &p[i].x, &p[i].y);
        p[i].id = i;
    }

    sort(p, p + N, cmp);

    for (int i = 0; i < N; i++) {
        vis.clear();
        for (int j = i + 1; j < N; j++)
            addEdge(p[i], p[j]);
    }
}

void bfs () {
    queue<int> que;
    que.push(0);
    memset(d, -1, sizeof(d));
    d[0] = 0;

    while (!que.empty()) {
        int u = que.front();
        que.pop();

        if (u == 1) {
            printf("%d\n", d[u]-1);
            return;
        }

        for (int i = 0; i < g[u].size(); i++) {
            int v = g[u][i];

            if (d[v] == -1) {
                d[v] = d[u] + 1;
                que.push(v);
            }
        }
    }
    printf("impossible\n");
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        init();
        bfs();
    }
    return 0;
}