比赛 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;
}