比赛 |
2025暑期集训第5场图论专场 |
评测结果 |
WEEEEEEEEEW |
题目名称 |
激光 |
最终得分 |
0 |
用户昵称 |
秋_Water |
运行时间 |
1.321 s |
代码语言 |
C++ |
内存使用 |
8.68 MiB |
提交时间 |
2025-07-09 11:40:17 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int mapp[1008][1008];
int vis[1008][1008][2];
int n, a, b, c, d;
int dx1[2] = {0, 0};
int dy1[2] = {1, -1};
int dx2[2] = {1, -1};
int dy2[2] = {0, 0};
struct node {
int x, y, t, zt;
};
int main() {
freopen("lasers.in","r",stdin);
freopen("lasers.out","w",stdout);
cin >> n >> a >> b >> c >> d;
memset(mapp, 0, sizeof(mapp));
for (int i = 1; i <= n; i++) {
int x, y;
cin >> x >> y;
mapp[x][y] = 2;
}
if (a == c && b == d) {
cout << 0 << endl;
return 0;
}
for (int i = 0; i <= 1000; i++)
for (int j = 0; j <= 1000; j++)
for (int k = 0; k < 2; k++)
vis[i][j][k] = INF;
queue<node> q;
vis[a][b][0] = 0;
vis[a][b][1] = 0;
q.push({a, b, 0, 0});
q.push({a, b, 0, 1});
while (!q.empty()) {
node now = q.front();
q.pop();
if (now.t > vis[now.x][now.y][now.zt])
continue;
int *dx, *dy;
if (now.zt == 1) {
dx = dx1;
dy = dy1;
} else {
dx = dx2;
dy = dy2;
}
for (int i = 0; i < 2; i++) {
int xx = now.x + dx[i];
int yy = now.y + dy[i];
if (xx < 0 || yy < 0 || xx > 1000 || yy > 1000)
continue;
if (mapp[xx][yy] == 2) {
int nzt = now.zt ^ 1;
int nt = now.t + 1;
if (vis[now.x][now.y][nzt] > nt) {
vis[now.x][now.y][nzt] = nt;
q.push({now.x, now.y, nt, nzt});
}
} else {
int nt = now.t + 1;
if (xx == c && yy == d) {
cout << nt << endl;
return 0;
}
if (vis[xx][yy][now.zt] > nt) {
vis[xx][yy][now.zt] = nt;
q.push({xx, yy, nt, now.zt});
}
}
}
}
cout << -1 << endl;
return 0;
}