题解：P15680 [ICPC 2024 Jakarta R] Mirror Maze

dxymemory · 2026-07-21 09:34:06 · 题解

哇，居然没有题解，那本蒟蒻要来交一发题解了！

题目简述

给出一个 R \times C 网格，该网格中的格子可能为空格和玻璃，请寻找可行的光线射入位置使得该光线可以经过所有的玻璃。

问题的基本分析

读完题之后第一反应就是搜索。我对搜索的一个理解 —— 如果一个题目我们可以确定其每一步发生的时候的状态的表示方法，可以得出状态之间的转移方式，状态数量在允许的时间复杂度内，便可以考虑使用搜索算法进行搜索，并在搜索的过程中求解得到答案。

观察数据范围可以得知 1 \leq R \leq 200 且 1 \leq C \leq 200，因此总共有 40000 个格子。对于每个格子一共有4种不同的情况 —— 从上下左右四个方向射进来光线，以及四个方向射出来光线。所以对于每个格子一共有 8 \times 40000 = 320000 种情况。但是！

引理（光路可逆性）

光线在网格中传播满足可逆性质：若光线从某一方向射入格子、从另一方向射出，则反向沿出射方向射入同一格子时，必然沿原入射方向射出。

证明

网格仅包含空格与玻璃两类格子，空格仅直线透光、玻璃遵循固定反射规则，二者对光线的作用均双向对称，不存在单向传播限制。例如光线自上方射入空格、从下方穿出，反之自下方射入空格，光线必然从上方穿出；玻璃反射规则同理可逆。

有关光线射入与射出，从上面的引理可以得知对于光线而言方向并不重要，对于一个格子而言，如果从上面射入的光线可以从下面射出，那么对于该格子来说从下面射入的光线也一定可以从上面射出，所以我们只需要讨论对于某个格子而言光线经过它的哪个方向即可，因此实际上只有 4 \times 40000 = 16000 种情况。

我们可以将这些不同的情况设置为状态，于是我们便可以发现，我们可以使用一个三元组 (x,y,c) 来表示一个状态。其含义为在坐标为 x,y 的格子上有一个从方向 c 射入进来的光线。

基于此剩下的问题便是怎么进行状态的转移。

状态转移的讨论

首先定义方向 c ，我们可以假设对于左下右上四个方向将 c 分别设置为 0,1,2,3 。 并且设置 dc 为 c 相反方向的光线。因此对于 c 与 dc 的值对应关系如下:

于是得到 dc = (c + 2) \bmod 4 又或者 dc = c \oplus 2 。

先讨论射出的光线的情况。

对于空白格子

假设 (x,y) 是空白格子，那么对于从下面射入的光线，也就是 (x-1,y,1) 的状态，也会从当前格子的上面射出去，所以 (x-1,y,1) \to (x,y,1) 。

所以同理，对于从 c 方向射入的光线，也一定会从该空白格子的同一个方向射出。所以得到如下式子。

上面的式子是谁可以转移到 (x,y,c) , 那么根据上面的我们也可以反过来讨论。 也就是说对于状态(x,y,c) 将要转移到空白格子的时候。（注意，下面的式子左边的三元组不代表 (x,y) 是空白格子，它的含义仅仅是从 (x,y) 的格子射出一个方向为 c 的光线，右边的才是空白格子）。

同时我们发现，对于不同的 c 右边的增量是固定的，所以我们可以仿照 bfs 跑迷宫的方法写增量数组，设置：

int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

于是上面的式子可以被写为：

也就是说对于在坐标 (x,y) 位置的格子，以 c 方向射出光线，最终会被 (x + dx[c],\ y + dy[c]) 的位置格子接收，并且以 c 的方向射出。

有关 \backslash 型玻璃的讨论

类似于空白格子的讨论方法，如果上面看懂了，那么接下来就很快了。

讨论对于 (x,y,c) 到达的新的格子的位置是 \backslash 型玻璃，那么根据光路反射示意图可以得知，

于是 c 的变化可以概括为奇数 -1 偶数 +1 ，也可以写个数组进行映射，也可以通过观察发现，每次只有二进制的最低位发生变化，所以可以用 c \oplus 1 来得到：

有关 / 型玻璃的讨论

下面同理，不再过多赘述。

于是 c 的变化可以概括为奇数 +1 偶数 +3 然后 \bmod 4 ，也可以写个数组进行映射，也可以通过观察发现对于二进制的最后一位和倒数第二位发生了变化，所以也可以用 c \oplus 3 来得到：

对于入射光线的讨论

根据光路可逆性，可以得知，当我们进行射出光线的状态转移的时候，应该同步进行入射光线的状态标记。

详细来说，当我们从 (x,y) 转移到 (x + dx[c],\ y + dy[c]) 的时候，除了要处理从 (x + dx[c],\ y + dy[c]) 的射出光线的方向，还要处理射入 (x + dx[c],\ y + dy[c]) 光线的方向，因为只有这样子才是可逆的，而对于入射方向，一定是通过上一个状态的 dc 得到（往上射出的光线，对于上面的格子来说是从下面射上来的，所以是相反方向），只有这样子我们才可以让光线完整。

因此当进行状态转移的时候我们还需要标记 (x + dx[c],\ y + dy[c],dc)。

搜索的讨论

光路的环与链基础性质

网格内所有光路只有两种形态：链、环，二者互斥，不存在一条光路同时包含环与链。

引理

若光线的传播路径中出现重复状态 (x,y,c)，则光路形成闭环；处于闭环内的光线会无限循环，永远无法抵达网格边界。

证明

全部合法状态仅有 R \times C \times 4 种，光线持续传播必然重复访问某个三元组状态。又由光路可逆性，一旦重复到达同一状态，后续路径会完全复刻此前循环轨迹，形成封闭环路，光线无法穿出网格边界。

反之，若光路属于链结构，则路径不存在重复状态，最终一定会抵达网格边界，存在合法入射/出射端口。

优化枚举思路

假设枚举起点进行搜索，那么一共有 R + C 种不同的入射起点，那么时间复杂度来到 O(R \times C \times 4 \times (R + C)) 很明显会超时。

考虑优化起点的枚举，因为要求是找出入射位置，使得所有玻璃被经过。所以我们改为假设某个玻璃通过某个方向被经过，那么共有4个方向。又因为根据光路可逆性可以得知，有两条方向光线肯定是可逆的。所以实际上只有两个方向，并且一定是两个相反的方向。

所以枚举任意一块玻璃的两个相反的方向射出光线，并且进行搜索，如果经过了所有玻璃并且达到了边界则说明这个方向是正确的，反之则不对。

因此只需要枚举两次，时间复杂度降低至 O(R \times C \times 4 \times 2) 很明显可以接受。

判断是否正确

对于如何判断当前这个搜索是否正确，假设我们在枚举方向 0 的时候应当枚举当前玻璃的折射方向，也就是两个状态同步进行。将经过的玻璃打上标记，并且将经过的边界也打上标记。在搜索完之后判断是否经过了所有的玻璃并且有两个边界即可。

关于解的数量的讨论

该题只可能有 0、2、4 种不同的入射方向作为答案，并且当且仅当只有一个玻璃的时候才可能存在答案为4的解。

解释如下：

关于答案为4的情况下只有一个玻璃的解释如下：

若想出现两组互不重合、独立满足题意的光路（合计 4 个入射点），需要存在两条完全独立、互不相交的完整光路，两条光路各自遍历全部玻璃。

当网格玻璃数量大于 1 时，任意两条覆盖全部玻璃的光路必然共用大量玻璃；对光路整体反向只会得到同一条光路的逆路径，无法产生全新独立光路，因此最多只有一组共轭光路，对应 2 个入射解。

只有网格仅存在 1 块玻璃时，单块反射镜存在两组互不重叠、独立完整的光路，两组光路各自可逆，合计产生 4 个不同的边界入射位置，也就是唯一能出现 4 解的场景。

到这里就可以愉快的写代码啦！因为篇幅过长，所以将代码解析和完整代码放入折叠块中。

::::info[代码解析]

我的基础框架

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,k,T;

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    return 0;
}

创建的全局变量

int dt[210][210] = {};
int hx[210][210][4] = {}; // 0R 1D 2L 3U 射入射出的方向无所谓
vector<pair<char,int>> ans;

// 顺序不要错，这是为了方便接下来的bfs
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int sum = 0;// 表示总共有多少个玻璃

处理输入，详细的可以看注释

cin >> n >> m;
int a,b;
// 读入数据，将玻璃转化为数字，设置好方向以及转换规则
int sum = n * m; // 统计有几块玻璃
for(int i = 1;i <= n; ++ i) {
  for(int j = 1;j <= m; ++ j) {
    char c;
    cin >> c;
    if(c == '.') dt[i][j] = 0,sum--;
    else if(c == '/') dt[i][j] = 1; // 0<->1 2<->3 
    else dt[i][j] = 2; // 0<->3 2<->1
    if(dt[i][j]) a = i,b = j; //记录最后一块玻璃的位置
  }
}

编写 bfs 函数进行搜索

void bfs(int x,int y,int a) {
  queue<pair<int,int> > qe; // 存储当前的坐标
  queue<int> qc; // 存储当前方向
  hx[x][y][a] = 1; // 记录当前某个方向是否被走过
  qe.push({x,y}); // 存入对于当前枚举方向的两条光线
  if(dt[x][y] == 1) hx[x][y][(a+1)] = 1,qc.push(a+1);
  else hx[x][y][(a+3)%4] = 1,qc.push((a+3)%4);
  qe.push({x,y});
  qc.push(a);   
}

用于辅助bfs的函数

// 如果该玻璃有被标记过则设置返回true，反之返回false
bool get(int x,int y) {
    return (hx[x][y][0] || hx[x][y][1] || hx[x][y][2] || hx[x][y][3]);
}

// 判断有没有越界
bool check(int x,int y) {
    return x > 0 && x <= n && y > 0 && y <= m;
}

bfs的循环部分

while(!qe.empty()) {
  int x = qe.front().first,y = qe.front().second;qe.pop();
  int c = qc.front();qc.pop();
  int dx = x + ::dx[c],dy = y + ::dy[c]; // 到达的点的坐标
  int dc = (c + 2) % 4; // 对应的从哪个方向进入dx、dy
}

如果在范围内

if(check(dx,dy)) { // 在范围内
  if(dt[dx][dy] == 0) { // 是空地 —— 0<->2 1<->3 —— (c + 2) % 4
    if(!hx[dx][dy][dc]) { // 从这里进来
      hx[dx][dy][dc] = 1;
      hx[dx][dy][c] = 1;
      qe.push({dx,dy});
      qc.push(c); // 出去方向一致
    }
  }
  else if(dt[dx][dy] == 1) { // 是 ‘/’ 玻璃 0<->1 2<->3 如果c是偶数+1，c是奇数-1
    int cc = c ^ 3;
    if(!hx[dx][dy][(c + 2) % 4] && !hx[dx][dy][cc]) { // 进来和出去的地方没走过
      hx[dx][dy][cc] = 1;
      hx[dx][dy][(c + 2) % 4] = 1;
      qe.push({dx,dy});
      qc.push(cc);
    }
  }
  else { // 是 ‘\’的玻璃 0<->3 2<->1 如果c是偶数-1，c是奇数+1 => 偶数+3%4 奇数+1%4
    int cc = c ^ 1; 
    if(!hx[dx][dy][(c + 2) % 4] && !hx[dx][dy][cc]) { // 进来和出去的地方没走过
      hx[dx][dy][cc] = 1;
      hx[dx][dy][(c + 2) % 4] = 1;
      qe.push({dx,dy});
      qc.push(cc);
    }
  }
}

不在范围内，到达边界

else { // 不在范围内，那么要做标记,方便找到答案去做判断
  // cerr << "ok" << endl;
  if(dx == 0) {
    ans.push_back({'N',dy});
  }
  if(dy == 0) {
    ans.push_back({'W',dx});
  }
  if(dx == n + 1) {
    ans.push_back({'S',dy});
  }
  if(dy == m + 1) {
    ans.push_back({'E',dx});
  }
}

主函数调用bfs找第一个方向

// 第1个方向
bfs(a,b,0);

// 统计答案是否正确，实际上可以在bfs中实现
int cnt = 0;
for(int i = 1;i <= n; ++ i) {
  for(int j = 1;j <= m; ++ j) {
    if(get(i,j) && dt[i][j]) { // 如果这处有玻璃并且走过的话
      cnt++;
    }
  }
}
if(cnt != sum) { // 不是答案清空数组
  ans.clear();
}

调用bfs找第二个方向，并且输出答案

memset(hx,0,sizeof(hx));
bfs(a,b,2);
cnt = 0;
for(int i = 1;i <= n; ++ i) {
  for(int j = 1;j <= m; ++ j) {
    if(get(i,j) && dt[i][j]) { // 如果这处有玻璃并且走过的话
      cnt++;
    }
  }
}
int num = ans.size();
if(cnt != sum) num -= 2;
cout << num << endl;
for(int i = 0;i < num; ++ i) {
  cout << ans[i].first << ans[i].second << ' ';
}

::::

::::info[完整代码]

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
int n,m,k,T;

int dt[210][210] = {};
int hx[210][210][4] = {}; // 0R 1D 2L 3U 射入射出的方向无所谓
vector<pair<char,int>> ans;

// 顺序不要错，这是为了方便接下来的bfs
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

int sum = 0;// 表示总共有多少个玻璃

// 如果该玻璃有被标记过则设置返回true，反之返回false
bool get(int x,int y) {
    return (hx[x][y][0] || hx[x][y][1] || hx[x][y][2] || hx[x][y][3]);
}

// 判断有没有越界
bool check(int x,int y) {
    return x > 0 && x <= n && y > 0 && y <= m;
}

// 针对 x,y处如果有玻璃，那么判断该处的光是否走过，a表示方向，并且方向只会是0/2
void bfs(int x,int y,int a) {
    queue<pair<int,int> > qe; // 存储当前的坐标
    queue<int> qc; // 存储当前玻璃的方向
    hx[x][y][a] = 1; // 记录当前某个方向是否被走过
    qe.push({x,y});
    if(dt[x][y] == 1) hx[x][y][(a+1)] = 1,qc.push(a+1);
    else hx[x][y][(a+3)%4] = 1,qc.push((a+3)%4);
    qe.push({x,y});
    qc.push(a);     
    while(!qe.empty()) {
        int x = qe.front().first,y = qe.front().second;qe.pop();
        int c = qc.front();qc.pop();
        // cerr << x << " " << y << ' ' << c << endl;
        int dx = x + ::dx[c],dy = y + ::dy[c];
        int dc = (c + 2) % 4; // 对应的从哪个方向进入dx、dy
        if(check(dx,dy)) { // 在范围内
            if(dt[dx][dy] == 0) { // 是空地 —— 0<->2 1<->3 —— (c + 2) % 4
                if(!hx[dx][dy][dc]) { // 从这里进来
                    hx[dx][dy][dc] = 1;
                    hx[dx][dy][c] = 1;
                    qe.push({dx,dy});
                    qc.push(c); // 出去方向一致
                }
            }
            else if(dt[dx][dy] == 1) { // 是 ‘/’ 玻璃 0<->1 2<->3 如果c是偶数+1，c是奇数-1
                int cc = c ^ 3;
                if(!hx[dx][dy][(c + 2) % 4] && !hx[dx][dy][cc]) { // 进来和出去的地方没走过
                    hx[dx][dy][cc] = 1;
                    hx[dx][dy][(c + 2) % 4] = 1;
                    qe.push({dx,dy});
                    qc.push(cc);
                }
            }
            else { // 是 ‘\’的玻璃 0<->3 2<->1 如果c是偶数-1，c是奇数+1 => 偶数+3%4 奇数+1%4
                int cc = c ^ 1; 
                if(!hx[dx][dy][(c + 2) % 4] && !hx[dx][dy][cc]) { // 进来和出去的地方没走过
                    hx[dx][dy][cc] = 1;
                    hx[dx][dy][(c + 2) % 4] = 1;
                    qe.push({dx,dy});
                    qc.push(cc);
                }
            }
        }
        else { // 不在范围内，那么要做标记,方便找到答案去做判断
            // cerr << "ok" << endl;
            if(dx == 0) {
                ans.push_back({'N',dy});
            }
            if(dy == 0) {
                ans.push_back({'W',dx});
            }
            if(dx == n + 1) {
                ans.push_back({'S',dy});
            }
            if(dy == m + 1) {
                ans.push_back({'E',dx});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    int a,b;
    // 读入数据，并且将玻璃转化为数字，并且设置好方向以及转换规则
    int sum = n * m; // 统计有几块玻璃
    for(int i = 1;i <= n; ++ i) {
        for(int j = 1;j <= m; ++ j) {
            char c;
            cin >> c;
            if(c == '.') dt[i][j] = 0,sum--;
            else if(c == '/') dt[i][j] = 1; // 0<->1 2<->3 
            else dt[i][j] = 2; // 0<->3 2<->1
            if(dt[i][j]) a = i,b = j;
        }
    }
    // 第1个方向
    bfs(a,b,0);

    // 统计答案是否正确，实际上可以在bfs中实现，等待以后再试试
    int cnt = 0;
    for(int i = 1;i <= n; ++ i) {
        for(int j = 1;j <= m; ++ j) {
            if(get(i,j) && dt[i][j]) { // 如果这处有玻璃并且走过的话
                cnt++;
            }
        }
    }
    if(cnt != sum) {
        ans.clear();
    }
    //第二个方向
    memset(hx,0,sizeof(hx));
    bfs(a,b,2);
    cnt = 0;
    for(int i = 1;i <= n; ++ i) {
        for(int j = 1;j <= m; ++ j) {
            if(get(i,j) && dt[i][j]) { // 如果这处有玻璃并且走过的话
                cnt++;
            }
        }
    }
    int num = ans.size();
    if(cnt != sum) num -= 2;
    cout << num << endl;
    for(int i = 0;i < num; ++ i) {
        cout << ans[i].first << ans[i].second << ' ';
    }
    return 0;
}

::::