acdream 1681(bfs)

题意：有一条河，河中有n个石头，给出了河的宽度和石头的位置，一个人要渡河，给出了这个人最远跳多远。问最少跳几下跳到对岸，或者如果跳不到那么就输出可以离对岸最近的距离。

题解：bfs，直接暴力把所有可能跳的情况都过一遍就可以找到解了。

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1005;
struct P {
	int x, y, step, id;
}p[N];
int yy, n;
double d;
queue<P> q;

bool cmp(P a, P b) {
	if (a.y != b.y)
		return a.y < b.y;
	return a.x < b.x;
}

double dist(P a, P b) {
	if (b.id != n + 1)
		return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
	return fabs(b.y - a.y);
}

int bfs() {
	p[0].step = 0;
	int res = 0x3f3f3f3f, minn = 0;
	for (int i = 1; i <= n + 1; i++) {
		if (p[i].y <= d) {
			p[i].step = 1;
			if (i == n + 1)
				return 1;
			q.push(p[i]);
		}
		else
			break;
	}
	while (!q.empty()) {
		P u = q.front();
		q.pop();
		minn = max(minn, u.y);
		for (int i = u.id + 1; i <= n + 1; i++) {
			if (dist(u, p[i]) - d <= 1e-7 && p[i].step > u.step + 1) {
				p[i].step = u.step + 1;
				if (i == n + 1)
					break;
				q.push(p[i]);
			}
			if (fabs(u.y - p[i].y) > d)//剪枝
				break;
		}
	}
	if (p[n + 1].step == 0x3f3f3f3f)
		return minn - yy;
	return p[n + 1].step;
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		while (!q.empty())
			q.pop();
		scanf("%d%d%lf", &yy, &n, &d);
		for (int i = 1; i <= n; i++) {
			scanf("%d%d", &p[i].x, &p[i].y);
			p[i].step = 0x3f3f3f3f;
		}
		sort(p + 1, p + 1 + n, cmp);
		p[0].y = 0;
		p[n + 1].y = yy;
		p[n + 1].step = 0x3f3f3f3f;
		for (int i = 0; i <= n + 1; i++)
			p[i].id = i;
		int res = bfs();
		if (res > 0)
			printf("YES\n%d\n", res);
		else
			printf("NO\n%d\n", -res);
	}
	return 0;
}

acdream 1681(bfs)

原文：http://blog.csdn.net/hyczms/article/details/45076653