社区讨论
哪里写错了,简单的二分+bfs
UVA12128 Escape from Enemy Territory参与者 2已保存回复 1
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 1 条
- 当前快照
- 1 份
- 快照标识符
- @loc3yl52
- 此快照首次捕获于
- 2023/10/30 07:34 2 年前
- 此快照最后确认于
- 2023/11/04 13:36 2 年前
CPP
#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???
回复
共 1 条回复,欢迎继续交流。
正在加载回复...