本文主要是介绍HDU 4885 TIANKENG’s travel（几何bfs)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
HDU 4885 TIANKENG’s travel
题目链接
题意：给定起点，终点，和一些加油站，要求路过最少的加油站到终点，两点距离必须小于L
思路：先建图，建图时把两点中间没有点，并且距离能到达的建一条长度1的边，那么问题就是如何判断中间没有点，先把所有点按x排序，然后每次找的时候，利用一个set存放当前已有向量，那么下次如果又出现肯定就是不能加入的点，利用set去搞，然后建完图就是简单的广搜了
代码：
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cstdlib>
#include <set>
#include <algorithm>
using namespace std;const int N = 1005;typedef long long ll;
typedef pair<int, int> pii;
#define MP(a,b) make_pair(a,b)vector<int> g[N];
int t, n, vis[N];
ll l;struct Point {ll x, y;int id;
} p[N];bool cmp(Point a, Point b) {if (a.x != b.x) return a.x < b.x;return a.y < b.y;
}ll gcd(ll a, ll b) {if (!b) return a;return gcd(b, a % b);
}bool dis(Point a, Point b) {ll dx = a.x - b.x;ll dy = a.y - b.y;return dx * dx + dy * dy <= l * l;
}void build() {sort(p, p + n + 1, cmp);for (int i = 0; i <= n + 1; i++) {set<pii> save;for (int j = i + 1; j <= n + 1; j++) {if (dis(p[i], p[j])) {ll dx = p[i].x - p[j].x;ll dy = p[i].y - p[j].y;ll d = gcd(dx, dy);dx /= d; dy /= d;if (save.find(MP(dx, dy)) != save.end()) continue;save.insert(MP(dx, dy));g[p[i].id].push_back(p[j].id);g[p[j].id].push_back(p[i].id);}}}
}bool solve() {queue<int> Q;memset(vis, -1, sizeof(vis));Q.push(0);vis[0] = 0;while (!Q.empty()) {int now = Q.front();if (now == n + 1) {printf("%d\n", vis[now] - 1);return true;}Q.pop();for (int i = 0; i < g[now].size(); i++) {int v = g[now][i];if (vis[v] != -1) continue;vis[v] = vis[now] + 1;Q.push(v);}}return false;
}int main() {scanf("%d", &t);while (t--) {scanf("%d%lld", &n, &l);scanf("%lld%lld", &p[0].x, &p[0].y);p[0].id = 0; p[n + 1].id = n + 1;scanf("%lld%lld", &p[n + 1].x, &p[n + 1].y);g[0].clear(); g[n + 1].clear();for (int i = 1; i <= n; i++) {g[i].clear();scanf("%lld%lld", &p[i].x, &p[i].y);p[i].id = i;}build();if (!solve()) printf("impossible\n");}return 0;
}这篇关于HDU 4885 TIANKENG’s travel（几何bfs)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
