Laserbox 遊戲模擬：鏡面反射路徑計算算法詳解

問題描述

Laserbox 是一個光學遊戲。棋盤為 n×n 方格 (1 ≤ n ≤ 50)。格點可放置「右轉器」，激光從邊界進入（底部向北、頂部向南、左側向東、右側向西）。右轉器將光線向右偏折 90°。給定右轉器位置和激光入射點，模擬光線路徑，輸出出射座標；若光線陷入循環無法出射，輸出 0 0。

座標系統規則

• 棋盤格點座標範圍：(1,1) 到 (n,n)。
• 激光位置表示：
  • 底部第 6 列：6 0 (向北)
  • 頂部第 6 列：6 n+1 (向南)
  • 左側第 7 行：0 7 (向東)
  • 右側第 7 行：n+1 7 (向西)
• 出射座標同理，X=0 或 n+1 表示左右出射，Y=0 或 n+1 表示上下出射。

核心算法：逐步模擬 + 循環檢測

狀態定義

光線狀態由 位置 (x,y) 和 方向 dir 唯一確定。方向編碼：0=北, 1=東, 2=南, 3=西。

模擬步驟

1. 根據入射座標確定 初始位置 (進入棋盤第一個格點) 和 初始方向。
2. 循環：
   1. 若當前位置超出棋盤範圍 (x<1 || x>n || y<1 || y>n) → 到達邊界，輸出出射座標 (根據出射邊計算)。
   2. 若當前狀態 (x,y,dir) 已訪問過 → 陷入循環，輸出 0 0。
   3. 標記當前狀態已訪問。
   4. 檢查當前格點 (x,y) 是否有右轉器：
      • 有：dir = (dir + 1) % 4 (右轉 90°)
      • 無：方向不變
   5. 根據方向移動一步：x += dx[dir]; y += dy[dir];

方向向量

// dir: 0=N, 1=E, 2=S, 3=W
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0}; // 注意：y 向下增或向上增視座標系，此處假設 y 向北減
// 入射邊界映射：
// 底部 (y=0) -> 進入 (x,1) 方向北(0)
// 頂部 (y=n+1) -> 進入 (x,n) 方向南(2)
// 左側 (x=0) -> 進入 (1,y) 方向東(1)
// 右側 (x=n+1) -> 進入 (n,y) 方向西(3)

複雜度分析

• 狀態空間大小：n * n * 4 ≤ 50*50*4 = 10,000。
• 每步 O(1)，最多走完所有狀態或出射。時間 O(n^2)，空間 O(n^2)，極易滿足限制。

C++ 參考實現

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, r; cin >> n >> r;
        vector<vector<bool>> turner(n+1, vector<bool>(n+1, false));
        for (int i = 0; i < r; ++i) {
            int x, y; cin >> x >> y;
            turner[x][y] = true;
        }
        int lx, ly; cin >> lx >> ly; // 激光位置

        // 確定起始點和方向
        int x, y, dir;
        if (ly == 0) { x = lx; y = 1; dir = 0; }           // 底部向北
        else if (ly == n+1) { x = lx; y = n; dir = 2; }    // 頂部向南
        else if (lx == 0) { x = 1; y = ly; dir = 1; }      // 左側向東
        else { x = n; y = ly; dir = 3; }                   // 右側向西 (lx == n+1)

        const int dx[4] = {0, 1, 0, -1};
        const int dy[4] = {-1, 0, 1, 0};
        vector<vector<array<bool,4>>> vis(n+1, vector<array<bool,4>>(n+1, {false,false,false,false}));

        while (true) {
            // 檢查是否出界
            if (x < 1 || x > n || y < 1 || y > n) {
                // 計算出射座標
                int ox = x, oy = y;
                if (x < 1) ox = 0;
                else if (x > n) ox = n+1;
                if (y < 1) oy = 0;
                else if (y > n) oy = n+1;
                cout << ox << " " << oy << "\n";
                break;
            }
            // 檢查循環
            if (vis[x][y][dir]) {
                cout << "0 0\n";
                break;
            }
            vis[x][y][dir] = true;

            // 遇到右轉器
            if (turner[x][y]) {
                dir = (dir + 1) % 4;
            }
            // 移動
            x += dx[dir];
            y += dy[dir];
        }
    }
    return 0;
}

樣例測試

輸入:
2
2 3
1 1
1 2
2 2
3 1
3 6
1 1
1 3
2 2
2 3
3 1
3 2
2 0

輸出:
2 0
0 2

第一組：3x3? 實際 n=2, 右轉器 (1,1)(1,2)(2,2)，激光 (3,1) 即右側第1行向西入射 -> 模擬得出射 (2,0) 底部第2列。
第二組：n=3, 激光 (2,0) 底部第2列向北 -> 出射 (0,2) 左側第2行。

關鍵點總結

• 座標映射是核心難點，需仔細處理邊界進入/出射座標轉換。
• 狀態 = (位置, 方向)，用 3D 數組或 Set 記錄訪問狀態檢測循環。
• 右轉器邏輯簡單：dir = (dir+1)%4。