M. 镜子迷宫 详细题解

问题重述

给定一个 $R \times C$ 的网格，每个格子可以是空（.）、/ 型镜子或 \ 型镜子。从网格外部边界（北、南、西、东）的某个位置发射一束激光，激光沿直线传播，遇到镜子则按照反射定律改变方向。要求激光束最终经过所有镜子（即每个镜子至少被击中一次）。问有多少个边界起始点满足条件，并输出它们。

关键观察

• 网格尺寸很小（$R, C \le 200$），因此状态总数有限。
• 激光的传播路径由当前位置和方向唯一决定。每个状态可以表示为 (r, c, dir)，其中 dir 表示进入当前格子的方向（北、南、西、东），或者更自然地，表示离开的方向。但为了模拟，我们常用“进入方向”或“在格子内部的方向”。
• 由于反射定律，光线在镜子格子中转向是确定的。在空格子中，光线保持原方向穿出到相邻格子。
• 光线可能进入循环（无限循环），也可能最终从边界射出。但题目要求所有镜子都被击中，因此我们需要检查路径是否经过所有镜子。

建模方法（拆点建图）

将每个格子 $(r,c)$ 拆分成 4 个节点，分别代表光线从该格子的北、南、西、东方向进入（或离开）的状态。但更常见的做法是：每个格子有 4 个“端口”：北、南、西、东。每个端口对应一个节点。然后根据格子类型连接这些端口：

• 空单元格 .：
  北端口连接到南端口（表示光线从北进入则从南穿出），
  南端口连接到北端口，
  西端口连接到东端口，
  东端口连接到西端口。
  即：光线直穿，方向不变。

• 类型 1 镜子 /：
  北端口连接到西端口，
  西端口连接到北端口，
  南端口连接到东端口，
  东端口连接到南端口。
  因为从北进入会被反射到西，从西进入反射到北，等等。

• 类型 2 镜子 \：
  北端口连接到东端口，
  东端口连接到北端口，
  南端口连接到西端口，
  西端口连接到南端口。

此外，相邻格子之间需要连接端口：

• 格子 $(r,c)$ 的南端口与格子 $(r+1,c)$ 的北端口相连（表示从上方格子向南离开，则进入下方格子的北边）。
• 同理，北端口与上方格子的南端口相连；西端口与左方格子的东端口相连；东端口与右方格子的西端口相连。

这样，整个网格就构成了一个有向图（实际上是无向边，但光线方向是确定的）。每个边界入口对应一个“外部节点”：例如从北侧第 $c$ 列射入，对应格子 $(1,c)$ 的北端口（进入方向为北）。然后沿着图走，直到离开网格（到达边界出口）。我们需要统计所有这样的入口，使得在路径中经过的所有节点中，包含所有镜子格子对应的至少一个端口（因为每个镜子只要被击中一次就算，无论从哪个方向）。但注意，镜子位于格子内部，我们只需要该格子被访问过即可。因此，我们可以记录每个格子是否被访问（即是否经过其任意一个端口）。

由于图规模小（节点数 $4RC \le 160000$），我们可以对每个边界入口进行 BFS/DFS，但直接做 $2(R+C)$ 次遍历会超时？ $2(R+C) \le 800$，每次 BFS 复杂度 $O(节点数)$，总 $O(800 \times 160000) = 1.28\times 10^8$，勉强可以接受，但常数较大。更好的方法是预处理所有光线路径，因为图是确定性的（每个节点出度为 1），实际上整个图是由若干条链和环组成。可以一次遍历所有节点，计算每个路径上的格子集合，然后对于每条路径，其边界入口是唯一的（如果路径从边界开始）或没有入口（环）。这样只需一次 DFS 标记每个节点属于哪条路径，并统计路径上的镜子集合。最后检查每条从边界出发的路径是否包含所有镜子。

由于题目要求输出所有满足条件的入口，且网格尺寸小，直接模拟每条光线也是可行的。下面给出一种简单的模拟方法：

简单模拟法

1. 枚举所有 $2(R+C)$ 个边界入口：

   • 北侧：方向向下，起始位置 $(1, c)$，进入方向为 北（即从北边进入该格子）。
   • 南侧：方向向上，起始位置 $(R, c)$，进入方向为 南。
   • 西侧：方向向右，起始位置 $(r, 1)$，进入方向为 西。
   • 东侧：方向向左，起始位置 $(r, C)$，进入方向为 东。

2. 对于每个入口，模拟光线传播：

   • 维护当前格子坐标 $(r,c)$ 和当前运动方向（即从哪个方向进入该格子，或等价地，在格子内朝向哪个方向离开）。
   • 根据格子类型更新方向：
     • 空：方向不变。
     • /：若进入方向为北，则离开方向为西；南→东；西→北；东→南。
     • \：北→东；南→西；西→南；东→北。
   • 然后移动到相邻格子（根据离开方向），同时记录经过的格子（镜子）。
   • 直到光线离开网格（即下一步的格子坐标超出范围）或进入循环（比如之前已经访问过相同的状态 (r,c,dir)，说明陷入循环）。注意循环中可能已经经过了所有镜子，但若循环不包含所有镜子，则永远不会击中剩下的镜子。

3. 在模拟过程中，使用一个布尔数组 hit[r][c] 记录该格子是否被击中过。若最终所有镜子格子（即网格中不是 '.' 的格子）都被击中，则该入口合法。

4. 收集所有合法入口，输出数量和字符串。

由于每个格子最多被访问 4 次（每个方向一次），每条路径长度 ≤ 4RC，所以单次模拟复杂度 $O(RC)$，总复杂度 $O((R+C) \cdot RC)$，对于 $R,C\le 200$ 时，$800 \times 40000 = 32\times 10^6$，可以在 1 秒内完成（实际常数小，因为光线路径通常较短）。

实现细节

• 方向编码：使用 0=北（向上），1=南（向下），2=西（向左），3=东（向右）。这样便于计算移动后的坐标。
• 反射规则可以用查表实现。
• 注意边界：当光线从某个方向离开格子时，下一个格子的坐标和进入方向应正确对应。例如，从北方向离开格子 $(r,c)$，则下一个格子是 $(r-1,c)$，且进入方向为南（因为从上方格子的南边进入）。

参考代码

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

int R, C;
vector<string> grid;

// 方向: 0北,1南,2西,3东
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

// 反射表: [格子类型][进入方向] -> 离开方向
// 类型: 0=空, 1='/', 2='\'
int reflect[3][4] = {
    {0,1,2,3},     // 空: 不变
    {2,3,0,1},     // / : 北->西,南->东,西->北,东->南
    {3,2,1,0}      // \ : 北->东,南->西,西->南,东->北
};

int main() {
    cin >> R >> C;
    grid.resize(R);
    for (int i = 0; i < R; ++i) cin >> grid[i];

    // 记录镜子位置
    vector<pair<int,int>> mirrors;
    for (int i = 0; i < R; ++i)
        for (int j = 0; j < C; ++j)
            if (grid[i][j] != '.')
                mirrors.emplace_back(i, j);
    int total_mirrors = mirrors.size();

    vector<string> ans;

    // 枚举所有边界入口
    // 北侧: 列 c, 起始 (0, c-1), 方向南(1)
    for (int c = 1; c <= C; ++c) {
        int r = 0, col = c-1;
        int dir = 1; // 向南进入第一个格子
        vector<vector<bool>> hit(R, vector<bool>(C, false));
        bool ok = true;
        int steps = 0;
        // 模拟，限制步数防止无限循环 (最多 4*R*C 步)
        while (true) {
            // 当前格子
            if (r < 0 || r >= R || col < 0 || col >= C) break; // 已出界
            // 记录击中
            if (grid[r][col] != '.') hit[r][col] = true;
            // 获取格子类型
            int type;
            if (grid[r][col] == '.') type = 0;
            else if (grid[r][col] == '/') type = 1;
            else type = 2;
            // 反射得到离开方向
            int new_dir = reflect[type][dir];
            // 移动
            int nr = r + dr[new_dir];
            int nc = col + dc[new_dir];
            // 更新方向为进入下一个格子的方向（即相反方向）
            // 因为进入下一个格子时，方向应与离开方向相反
            dir = (new_dir ^ 1); // 0<->1, 2<->3
            r = nr;
            col = nc;
            steps++;
            if (steps > 4 * R * C + 5) { // 防止无限循环
                ok = false;
                break;
            }
        }
        if (ok) {
            // 检查是否所有镜子都被击中
            bool all_hit = true;
            for (auto [rr, cc] : mirrors) {
                if (!hit[rr][cc]) { all_hit = false; break; }
            }
            if (all_hit) {
                ans.push_back("N" + to_string(c));
            }
        }
    }

    // 南侧: 行 R, 列 c, 起始 (R-1, c-1), 方向北(0)
    for (int c = 1; c <= C; ++c) {
        int r = R-1, col = c-1;
        int dir = 0; // 向北进入
        vector<vector<bool>> hit(R, vector<bool>(C, false));
        bool ok = true;
        int steps = 0;
        while (true) {
            if (r < 0 || r >= R || col < 0 || col >= C) break;
            if (grid[r][col] != '.') hit[r][col] = true;
            int type = (grid[r][col] == '.') ? 0 : (grid[r][col] == '/') ? 1 : 2;
            int new_dir = reflect[type][dir];
            int nr = r + dr[new_dir];
            int nc = col + dc[new_dir];
            dir = (new_dir ^ 1);
            r = nr; col = nc;
            steps++;
            if (steps > 4*R*C+5) { ok = false; break; }
        }
        if (ok) {
            bool all_hit = true;
            for (auto [rr, cc] : mirrors) if (!hit[rr][cc]) { all_hit = false; break; }
            if (all_hit) ans.push_back("S" + to_string(c));
        }
    }

    // 西侧: 行 r, 列 1, 起始 (r-1, 0), 方向东(3)
    for (int r = 1; r <= R; ++r) {
        int row = r-1, col = 0;
        int dir = 3; // 向东进入
        vector<vector<bool>> hit(R, vector<bool>(C, false));
        bool ok = true;
        int steps = 0;
        while (true) {
            if (row < 0 || row >= R || col < 0 || col >= C) break;
            if (grid[row][col] != '.') hit[row][col] = true;
            int type = (grid[row][col] == '.') ? 0 : (grid[row][col] == '/') ? 1 : 2;
            int new_dir = reflect[type][dir];
            int nr = row + dr[new_dir];
            int nc = col + dc[new_dir];
            dir = (new_dir ^ 1);
            row = nr; col = nc;
            steps++;
            if (steps > 4*R*C+5) { ok = false; break; }
        }
        if (ok) {
            bool all_hit = true;
            for (auto [rr, cc] : mirrors) if (!hit[rr][cc]) { all_hit = false; break; }
            if (all_hit) ans.push_back("W" + to_string(r));
        }
    }

    // 东侧: 行 r, 列 C, 起始 (r-1, C-1), 方向西(2)
    for (int r = 1; r <= R; ++r) {
        int row = r-1, col = C-1;
        int dir = 2; // 向西进入
        vector<vector<bool>> hit(R, vector<bool>(C, false));
        bool ok = true;
        int steps = 0;
        while (true) {
            if (row < 0 || row >= R || col < 0 || col >= C) break;
            if (grid[row][col] != '.') hit[row][col] = true;
            int type = (grid[row][col] == '.') ? 0 : (grid[row][col] == '/') ? 1 : 2;
            int new_dir = reflect[type][dir];
            int nr = row + dr[new_dir];
            int nc = col + dc[new_dir];
            dir = (new_dir ^ 1);
            row = nr; col = nc;
            steps++;
            if (steps > 4*R*C+5) { ok = false; break; }
        }
        if (ok) {
            bool all_hit = true;
            for (auto [rr, cc] : mirrors) if (!hit[rr][cc]) { all_hit = false; break; }
            if (all_hit) ans.push_back("E" + to_string(r));
        }
    }

    // 输出
    cout << ans.size() << "\n";
    if (!ans.empty()) {
        for (size_t i = 0; i < ans.size(); ++i) {
            if (i) cout << " ";
            cout << ans[i];
        }
        cout << "\n";
    }
    return 0;
}

复杂度分析

• 最坏情况下，每个入口模拟的步数最多 $4RC$（每个方向每个格子一次），总入口数 $2(R+C)$，故总时间复杂度 $O((R+C) \cdot RC)$，对于 $R,C \le 200$，约 $800 \times 40000 = 3.2 \times 10^7$，在 1 秒内可行。
• 空间复杂度 $O(RC)$ 用于存储命中标记。

总结

本题的关键在于将光线传播建模为确定性状态机，并通过枚举所有边界入口进行模拟，检查是否访问了所有镜子。由于网格尺寸小，直接模拟即可。实现时注意方向转换和边界处理。