题意
给一个 \(n \times m\) 的二维char数组，由4种镜子组成，'\', '/', '-', '|'，镜面反射规则就是根据光线的方向和镜面的角度符合直觉的反射，然后有多组询问 \(q \leq 10^6\)，每次给定起始位置和光线方向，求该光会经过多少面不同的镜子的反射。
思路
首先根据数据范围，发现肯定需要预处理答案，然后每次 \(O(1)\) 回答，所以考虑如何进行预处理，首先显然预处理是开一个 \(ans[n][m][4]\) 的数组，把每个位置的4种方向对应答案都存起来。(注意:这里的 \(ans[i][j][k]\) 表示的是方向为 \(k\) 的光线正要射向 \(ch[i][j]\) 的镜子时，总的会反射过的镜子数。而题目询问时起点的镜子不算，所以询问时要先根据方向移动一格，才对应上前面设置的状态的含义)
然后需要一些性质，一束光在这个矩阵里要么是陷入死循环，要么就一定会射出去越界消失。所以需要分别处理这两种情况。
还有最重要的一个性质就是，因为光路可逆， 所以每个状态(即上面的总共 4nm种状态)，一定只对应一条光路，也就是光路之间一定是没有重合的。这就启示了，可以直接爆搜，爆搜出来的状态不会有重复的。
然后就到了如何把环与链单独抽出来的问题，这个也是本题的难点(题解里只是讲了思路，具体如何抽，感觉也是非常考察代码能力)。赛后看了别人的代码，发现了巧妙的抽法。
还是由于前面的性质，对于一个链，最终肯定是射向出界，所以我们可以反过来，从四个边界往里射入光线，这些状态一定是可以作为链的起点的，然后根据题意爆搜，直到再次出界为止。把过程中经历的所有状态全部存起来(可以用vector<tuple<int, int, int>>储存)，这些状态就是链上的状态，然后倒叙遍历状态，维护每个状态的前缀会反射过的镜子(实现上，我先用一个函数表示一个状态是否会反射到那个位置的镜子，再用一个set把反射到的镜子的位置存起来)，然后就处理好了链。
接下来考虑处理环，因为前面已经把所有可能的链都处理好，所以直接暴力 for 循环遍历总的 4nm种状态，如果有状态未访问过，说明这个状态一定在环上，直接从它开始再暴力dfs，直到又到达一个已经访问过的状态，说明环走完了，对这些状态全部反射过的镜子用set存一下，然后set的大小就是这个环上所有状态的答案。
最后的询问，先根据方向偏移一下，然后直接输出预处理的答案即可。代码细节如下:
点击查看代码
#include <bits/stdc++.h>
#define pii pair<int, int>
#define tii tuple<int, int, int>
#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<tii> 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<pii> 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<pii> 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];
// 从边界射入的光线一定是链
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<string, int> 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;
}