I-Mirror Maze_2024牛客暑期多校训练营1

题目大意

有一个 n × m 的矩形镜子迷宫，镜子有 “\, /, -, |” 四种，每种镜子有特定的光线反射方向，注意直接通过镜子的情况不算被反射。

有 q 个询问，每个询问给定一个点光源 (x, y, dir)，表示在 (x, y) 位置向 dir 方向发射一束光线，问经过足够的时间之后，这束光线被多少个不同的镜子反射过。

1 ≤ n, m ≤ 1000, 1 ≤ q ≤ 105

题解

因为光路可逆，所以不可能有光束分叉或者汇合的情况，所以所有的光束会构成若干个环和若干条链。

所以我们要做的就是把这些光环和光链抽出来，然后预处理出每个点光源的答案，询问就查表 O(1) 回答即可。

时间复杂度：O(nm + q)。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include 
#define pii pair
#define tii tuple
#define all(a) a.begin(), a.end()
using namespace std;
const int maxn = 1e3 + 10;
char ch[maxn][maxn];
int n, m, ans[maxn][maxn][4];
int vis[maxn][maxn][4];
vector vec;//存储经过了哪些镜子的哪些状态
bool istan(int x, int y, int dir) {  // 标记某个状态是否会经过镜子的反射
    char tem = ch[x][y];
    if (tem == '/' || tem == '\\')
        return 1;
    if (tem == '-' && (dir == 0 || dir == 1))
        return 1;
    if (tem == '|' && (dir == 2 || dir == 3))
        return 1;
    return 0;
}
void dfs(int x, int y, int dir) {
    // 根据题意模拟反射过程，越界（链）或者访问过（环）退出
    if (x < 1 || x > n || y < 1 || y > m)  // 链的退出条件
        return;
    if (vis[x][y][dir])  // 环的退出条件
        return;
    vec.push_back(tii(x, y, dir));
    vis[x][y][dir] = 1;
    if (ch[x][y] == '/') {
        if (dir == 0) {
            dfs(x, y + 1, 3);
        } else if (dir == 1) {
            dfs(x, y - 1, 2);
        } else if (dir == 2) {
            dfs(x + 1, y, 1);
        } else {
            dfs(x - 1, y, 0);
        }
    } else if (ch[x][y] == '\\') { //注意多加一个'\'
        if (dir == 0) {
            dfs(x, y - 1, 2);
        } else if (dir == 1) {
            dfs(x, y + 1, 3);
        } else if (dir == 2) {
            dfs(x - 1, y, 0);
        } else {
            dfs(x + 1, y, 1);
        }
    } else if (ch[x][y] == '-') {
        if (dir == 0) {
            dfs(x + 1, y, 1);
        } else if (dir == 1) {
            dfs(x - 1, y, 0);
        } else if (dir == 2) {
            dfs(x, y - 1, 2);
        } else
            dfs(x, y + 1, 3);
    } else if (ch[x][y] == '|') {
        if (dir == 0)
            dfs(x - 1, y, 0);
        else if (dir == 1)
            dfs(x + 1, y, 1);
        else if (dir == 2) {
            dfs(x, y + 1, 3);
        } else {
            dfs(x, y - 1, 2);
        }
    }
}
void solve1(int x, int y, int dir) {
    // 处理链
    vec.clear();
    dfs(x, y, dir);
    reverse(all(vec));  // 倒叙遍历状态更新答案
    set s;
    for (auto [a, b, c] : vec) {
        if (istan(a, b, c))
            s.insert(pii(a, b));
        ans[a][b][c] = s.size();
    }
}
void solve2(int x, int y, int dir) {
    // 处理环
    vec.clear();
    dfs(x, y, dir);
    set s;
    for (auto [a, b, c] : vec) {
        if (istan(a, b, c))
            s.insert(pii(a, b));
    }
    for (auto [a, b, c] : vec)
        ans[a][b][c] = s.size();  // 环上的答案都一样
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> ch[i][j];
    /***** 0，1，2，3分别表示为向上、下、左、右射入的光线 *****/
    // 从边界射入的光线一定是链
    for (int i = 1; i <= n; i++)
        solve1(i, 1, 3), solve1(i, m, 2);
    for (int j = 1; j <= m; j++)
        solve1(1, j, 1), solve1(n, j, 0);
    // 还未访问的状态，一定是环上的状态
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int k = 0; k < 4; k++)
                if (!vis[i][j][k]) {
                    solve2(i, j, k);
                }
    int q;
    cin >> q;
    map mp;
    mp["above"] = 0;
    mp["below"] = 1;
    mp["left"] = 2;
    mp["right"] = 3;
    while (q--) {
        int x, y;
        string str;
        cin >> x >> y >> str;
        // 先根据方向偏移一格
        int tem = mp[str];
        if (tem == 0)
            x--;
        else if (tem == 1)
            x++;
        else if (tem == 2)
            y--;
        else
            y++;
        cout << ans[x][y][tem] << "\n";
    }
    return 0;
}