哪里写错了,简单的二分+bfs
查看原帖
哪里写错了,简单的二分+bfs
461366
封禁用户楼主2021/7/23 08:32
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <utility>
using namespace std;

int n, X, Y, xi, yi, xr, yr, d[1005][1005], d2[1005][1005];
const int dx[] = {-1, 1, 0, 0};
const int dy[] = {0, 0, -1, 1};
queue<pair<pair<int, int>, int> > q;

int inside(int x, int y) {
	return (0 <= x && x < X && 0 <= y && y < Y);
}

int check(int jg) {
	if (d[xi][yi] < jg || d[xr][yr] < jg) return 0;
	q.push(make_pair(make_pair(xi, yi), 0));
	memset(d2, 0x3f, sizeof(d2));
	d2[xi][yi] = 0;
	while (q.size()) {
		int x = q.front().first.first, y = q.front().first.second, sep = q.front().second;
		q.pop();
		if (x == xr && y == yr) return 1;
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (inside(nx, ny) && d[nx][ny] >= jg && d2[nx][ny] > sep + 1) {
				d2[nx][ny] = sep + 1;
				q.push(make_pair(make_pair(nx, ny), d2[nx][ny]));
			}
		}
	}
	return 0;
}

void solve() {
	memset(d, 0x3f, sizeof(d));
	scanf("%d%d%d", &n, &X, &Y);
	scanf("%d%d%d%d", &xi, &yi, &xr, &yr);
	while (n--) {
		int x, y;
		scanf("%d%d", &x, &y);
		d[x][y] = 0;
		q.push(make_pair(make_pair(x, y), 0));
	}
	// 初始化
	while (q.size()) {
		int x = q.front().first.first, y = q.front().first.second, sep = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i], ny = y + dy[i];
			if (inside(nx, ny) && d[nx][ny] > sep + 1) {
				d[nx][ny] = sep + 1;
				q.push(make_pair(make_pair(nx, ny), d[nx][ny]));
			}
		}
	}
	// 二分
	int lft = 0, rgt = 0x3f3f3f3f, a1 = 0, a2 = abs(xi - xr) + abs(yi - yr);
	while (lft <= rgt) {
		int mid = (lft + rgt) / 2;
		if (check(mid)) {
			a1 = max(a1, mid);
			a2 = d2[xr][yr];
			lft = mid + 1;
		} else rgt = mid - 1;
	}
	printf("%d %d\n", a1, a2);
}

int main() {
	int q;
	scanf("%d", &q);
	while (q--) solve();
	return 0;
}

我这都和正解差不多了,为什么还是WA???

2021/7/23 08:32
加载中...