题解：2024牛客暑期多校第1场——I [Mirror Maze]

英文题干

There is an $𝑛×𝑚$ mirror maze, where there is a mirror on each grid. The mirrors are in one of the following four types:

''-'', the light from above or below will be reflected back, the light from left or right will continue going forward without being reflected, respectively;
''|'', the light from left or right will be reflected back, the light from above or below will continue going forward without being reflected, respectively;
''/'', the light from left, right, above, below will be reflected to go above, below, left, right, respectively;
''\'', the light from left, right, above, below will be reflected to go below, above, right, left, respectively.

Now there are 𝑞 light sources. Little G, the believer of the light, wants to know the numbers of different mirrors the emitted light will be reflected by within sufficient time for each light source.

Input:

The first line contains two integers $n,m(1\leq n,m\leq 1000)$ , denoting the size of the mirror maze.

Each of the following 𝑛 lines contains a string of length 𝑚, where the 𝑗-th character in the 𝑖-th line $S_{i,j}(S_{i,j}\in \{|,-,$ \ $,/,\})$ denotes the mirror on grid $(i,j)$ .

The next line contains an integer $q(1\leq q\leq 10^5)$ , denoting the number of light sources.

Each of the following 𝑞 lines contains two integers $u(1\leq u\leq n)$ , $v(1\leq v\leq m)$ and a string $dir(dir\in\{above,below,left,right\})$ , denoting that a light source is on grid $(u,v)$ and emits light going along the $dir$ direction. Specifically, the light will not be influenced by the mirror on grid $(u,v)$ initially.

Output:

Output 𝑞 lines each containing one integer, denoting the number of different mirrors the emitted light will be reflected by within sufficient time for each light source.

中文题干

在一个 $𝑛×𝑚$ 的镜像迷宫里，每个格子上都有一面镜子。这些镜子属于以下四种类型之一：

''-'', 从上方或下方射来的光线会被反射回去，而从左侧或右侧射来的光线会继续向前而不被反射；
''|'', 从左侧或右侧射来的光线会被反射回去，而从上方或下方射来的光线会继续向前而不被反射；
''/'', 从左侧、右侧、上方、下方射来的光线会被反射到上方、下方、左侧、右侧，分别；
''\'', 从左侧、右侧、上方、下方射来的光线会被反射到下方、上方、右侧、左侧，分别。

现在有 𝑞 个光源。小 G 是一名光的信徒，他想要知道每个光源发出的光线在足够时间内会被多少面不同的镜子反射。

思路

一道典型的记忆化搜索

由于所有的光路在镜子方向确定之后都是固定的，所以直接建图求出所有光路。从四个边界分别向内dfs并记录链长，走过的路径用vis记录。最后遍历全图单独处理环。
然后以单次 O(1) 的复杂度进行查询即可

AC代码

时间复杂度：O( $nm q$ )

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int infmin = 0xc0c0c0c0;
const int infmax = 0x3f3f3f3f;
const int maxn = 1010;

#define Above 0
#define Below 1
#define Left 2
#define Right 3

int n, m;
char ch[maxn][maxn];      // 原图
int ans[maxn][maxn][4];
array<int, 3> rule[256][4]; // 256代表能处理ASCII中的所有值 (或使用static关键字)
// int ans[maxn][maxn][4];

inline bool check(int x, int y)
{
    if (x >= 1 && x <= n && y >= 1 && y <= m)
        return 1;
    return 0;
}

vector<array<int, 3>> vis;   // 记录本轮dfs访问过的节点(实现记忆化)
set<pair<int, int>> mazeNum; // 记录本轮dfs所参与反射的镜子数
bool existRound;             // 检查环
void dfs(int x, int y, int dir)
{
    if (!check(x, y)) // 越界了
        return;

    if (ans[x][y][dir] != -1) // 遇到环
    {
        existRound = 1;
        return;
    }

    auto [dx, dy, nextDir] = rule[ch[x][y]][dir];
    ans[x][y][dir] = mazeNum.size();
    if (dir != nextDir) // 不记录类似"-,left""|,below"等直接穿过的情况
        mazeNum.insert({x, y});

    vis.push_back({x, y, dir});
    dfs(x + dx, y + dy, nextDir);
}

void process(int x, int y, int dir, bool round)
{ // round表示是否是环
    mazeNum.clear();
    vis.clear();
    existRound = round;
    dfs(x, y, dir);
    if (existRound) // 遇到环就计算环的长度（vis数组的长度）
    {
        for (auto [a, b, c] : vis)
        {
            ans[a][b][c] = mazeNum.size();
        }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    // 创建链规则
    rule['-'][Above] = {-1, 0, Below}; // 表示above方向（从下往上）射来的光线在'-'上的反射情况
    rule['-'][Below] = {1, 0, Above};
    rule['-'][Left] = {0, 1, Left};
    rule['-'][Right] = {0, -1, Right};

    rule['|'][Above] = {1, 0, Above};
    rule['|'][Below] = {-1, 0, Below};
    rule['|'][Left] = {0, -1, Right};
    rule['|'][Right] = {0, 1, Left};

    rule['/'][Above] = {0, -1, Right};
    rule['/'][Below] = {0, 1, Left};
    rule['/'][Left] = {-1, 0, Below};
    rule['/'][Right] = {1, 0, Above};

    rule['\\'][Above] = {0, 1, Left};
    rule['\\'][Below] = {0, -1, Right};
    rule['\\'][Left] = {1, 0, Above};
    rule['\\'][Right] = {-1, 0, Below};

    // 输入图
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> ch[i][j];
        }
    }
    // 初始化记忆化数组
    memset(ans, -1, sizeof(ans));

    // 四个边界进入遍历
    for (int i = 1; i <= n; i++)
    {
        process(i, 1, Left, 0);
    }
    for (int i = 1; i <= n; i++)
    {
        process(i, m, Right, 0);
    }
    for (int j = 1; j <= m; j++)
    {
        process(1, j, Above, 0);
    }
    for (int j = 1; j <= m; j++)
    {
        process(n, j, Below, 0);
    }
    // 寻找未被遍历的环
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            for (int dir = 0; dir < 4; dir++)
            {
                if (ans[i][j][dir] == -1)
                {
                    process(i, j, dir, 1);
                }
            }
        }
    }

    int t;
    cin >> t;
    while (t--)
    {
        int xx, yy, op;
        string s;
        cin >> xx >> yy >> s;
        if (s[0] == 'a')
            op = 0;
        if (s[0] == 'b')
            op = 1;
        if (s[0] == 'l')
            op = 2;
        if (s[0] == 'r')
            op = 3;

        cout << ans[xx][yy][op] << "\n";
    }
    return 0;
}
// Inspired by Mocopentas