雷射測試 題解｜APCS 2022 年 6 月中高級 第 3 題

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 250000;
int x[MAX_N], y[MAX_N], type[MAX_N];
const int DX[4] = {1, 0, -1, 0};             // 方向 0 右、1 上、2 左、3 下
const int DY[4] = {0, 1, 0, -1};
const int SLASH[4] = {1, 0, 3, 2};           // 碰到 /：右變上、上變右、左變下、下變左
const int BACKSLASH[4] = {3, 2, 1, 0};       // 碰到 \：右變下、下變右、左變上、上變左

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i] >> type[i];
    int cx = 0, cy = 0, dir = 0;             // 目前位置與方向
    int count = 0;
    while (true) {
        int best = -1, bestDist = 0;
        for (int i = 0; i < n; i++) {        // 掃過所有鏡子，找「在前方」且最近的
            int dist = (x[i] - cx) * DX[dir] + (y[i] - cy) * DY[dir];   // 沿前進方向的距離
            bool sameLine = (DX[dir] != 0) ? (y[i] == cy) : (x[i] == cx);
            if (sameLine && dist > 0 && (best == -1 || dist < bestDist)) {
                best = i;
                bestDist = dist;
            }
        }
        if (best == -1) break;               // 前方沒有鏡子，結束
        count++;
        cx = x[best];
        cy = y[best];
        if (type[best] == 0) dir = SLASH[dir];
        else dir = BACKSLASH[dir];
    }
    cout << count << endl;
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 250000;
const int SLASH[4] = {1, 0, 3, 2};           // 碰到 /：右變上、上變右、左變下、下變左
const int BACKSLASH[4] = {3, 2, 1, 0};       // 碰到 \：右變下、下變右、左變上、上變左

struct Mirror {
    int x, y, type;
};
Mirror mir[MAX_N];
int nxt[MAX_N][4];                           // nxt[i][d] = 從第 i 面鏡子往方向 d 走，碰到的下一面鏡子（-1 = 沒有）
int order[MAX_N];

bool byRow(int a, int b) {                   // 同一列（y 相同）的鏡子照 x 排在一起
    if (mir[a].y != mir[b].y) return mir[a].y < mir[b].y;
    return mir[a].x < mir[b].x;
}
bool byColumn(int a, int b) {                // 同一行（x 相同）的鏡子照 y 排在一起
    if (mir[a].x != mir[b].x) return mir[a].x < mir[b].x;
    return mir[a].y < mir[b].y;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> mir[i].x >> mir[i].y >> mir[i].type;
        order[i] = i;
        for (int d = 0; d < 4; d++) nxt[i][d] = -1;
    }
    sort(order, order + n, byRow);
    for (int k = 0; k + 1 < n; k++) {
        int a = order[k], b = order[k + 1];
        if (mir[a].y == mir[b].y) {          // 同一列裡相鄰的兩面：互為左右鄰居
            nxt[a][0] = b;                   // a 往右碰到 b
            nxt[b][2] = a;                   // b 往左碰到 a
        }
    }
    sort(order, order + n, byColumn);
    for (int k = 0; k + 1 < n; k++) {
        int a = order[k], b = order[k + 1];
        if (mir[a].x == mir[b].x) {          // 同一行裡相鄰的兩面：互為上下鄰居
            nxt[a][1] = b;                   // a 往上碰到 b
            nxt[b][3] = a;                   // b 往下碰到 a
        }
    }
    int cur = -1;                            // 第一面：y = 0 上 x 最小的那面
    for (int i = 0; i < n; i++) {
        if (mir[i].y == 0 && (cur == -1 || mir[i].x < mir[cur].x)) cur = i;
    }
    int dir = 0, count = 0;
    while (cur != -1) {
        count++;
        if (mir[cur].type == 0) dir = SLASH[dir];
        else dir = BACKSLASH[dir];
        cur = nxt[cur][dir];
    }
    cout << count << endl;
    return 0;
}