Link

华中师范大学2023新生赛 I 镜面折跃

Question

懒得转述了

Solution

确实是一道好题

可以把一节方格拆成 \(4\) 个点，每个点分别代表从四个方向射进这个节点的光线

如果没有镜子，那么就左侧节点的右侧连接自己的右侧，以此类推

如果有镜子，那么顺着镜子方向建边，边权为 \(0\) ，向 \(90^{o}\) 方向建边，边权为 \(1\)

建边之后跑 01BFS

Code

来自某位大佬

#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
    cin.tie(0)->sync_with_stdio(false);
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n + 5, vector<int>(m + 5, -1));
    vector ok = a;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ok[i][j] = 1;
        }
    }
    ok[n][m + 1] = 1;
    for (int i = 1; i <= k; i++) {
        int x, y, t;
        cin >> x >> y >> t;
        a[x][y] = t;
    }
    using tup = tuple<int, int, int>;
    deque<tup> q;
    const vector<pair<int, int>> dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int inf = 1e9;
    vector<vector<vector<int>>> dis(n + 5, vector<vector<int>>(m + 5, vector<int>(5, inf)));
    dis[1][1][0] = 0;
    q.emplace_back(1, 1, 0);
    while (q.size()) {
        auto [x, y, u] = q.front();
        q.pop_front();
        if (a[x][y] == -1) {
            auto [dx, dy] = dir[u];
            int tx = x + dx, ty = y + dy;
            if (ok[tx][ty] == -1) continue;
            if (dis[x][y][u] < dis[tx][ty][u]) {
                dis[tx][ty][u] = dis[x][y][u];
                q.emplace_front(tx, ty, u);
            }
        } else {
            for (int t : {0, 1}) {
                int w = (t != a[x][y]);
                int nu = u ^ (1 + t + t);
                auto [dx, dy] = dir[nu];
                int tx = x + dx, ty = y + dy;
                if (ok[tx][ty] == -1) continue;
                if (dis[x][y][u] + w < dis[tx][ty][nu]) {
                    dis[tx][ty][nu] = dis[x][y][u] + w;
                    if (w == 0) q.emplace_front(tx, ty, nu);
                    else q.emplace_back(tx, ty, nu);
                }
            }
        }
    }
    int res = dis[n][m + 1][0];
    if (res > inf / 2) res = -1;
    cout << res << '\n';
    return 0;
}

Summary

• 可以用异或来代表左转或者右转，例如 右：\(0\)，下：\(1\)，左：\(2\)，上：\(3\)
  那么 \(t=0\) 表示左转，\(t=1\) 表示右转，\(u\) 代表现在的方向，\(nxt\) 代表接下来的方向，\(nxt=u \oplus (1+t+t)\)

• 判断出界的情况可以以外开一个数组 \(ok\) 来判断

• 可以不需要把点实际拆出来，用数组表示就可以了