摘要
Title: 1929. 镜子田地
Tag: 最长路、BFS、DFS、环图、镜子问题
Memory Limit: 64 MB
Time Limit: 1000 ms

1929. 镜子田地

题意

农夫约翰在屋子外面放了一些旧镜子，他的奶牛们像往常一样调皮地偷走了它们！
奶牛们将镜子放置在了一个矩形田地中，该田地可被划分为 N×M 个方格区域。
在每个方格区域中，奶牛在其某对对角之间放置一个双面镜，因此，共有两种放法，一种为 / 放置（镜子连接方格左下角和右上角），另一种为 \ 放置（镜子连接方格左上角和右下角）。
一天晚上，奶牛贝茜将激光发射器带到了该田地中。
她站在田地外面，沿着田地的行或列水平或垂直照射光束，使光束反射一定数量的镜子。
由于镜子都是沿对角线摆放，因此经反射镜反射的水平光束最终将垂直传播，反之亦然。
贝茜想知道从田地之外射入的水平或垂直光束最多可以在田地中被反射多少次。
给定镜子田地的布局，请帮助贝茜计算这个数字。
思路

将每个镜子拆成两个点，点和点之间形成一条边，故形成了图

有三种点
- 四个顶点，他们的度为 $0$ $0$
  - 即边角镜子的外面点
  - 因为光线进去就出来了
- 除去顶点的四个边，他们的度为 $1$
- 内部的点，他们的度为 $2$

这题相当于从边界点出发，最长的路径是多少（最长路）

可以用 spfa （但对于此题可能超时）

可以发现此图为环图

定义：某个无向图，所有点的度数都小于等于 2（特殊：都等于 2 时，是由若干个简单环构成）
性质：
- 由若干个简单环和简单路径构成（连通块要不是链就是环）（简单：不存在交叉）
- 暴力搜的话时间复杂度为线性
如何发现：
- 从度为 $1$ 的边界点出发，一定可以存在一个相邻点可以走（讨论点）
  - 如果这个相邻点是边界点，那么简单路径就完成了，后面不会有边了（光就出去了）
  - 如果这个相邻点是内部节点，因为这个节点的度数为 $2$ $2$ ，所以一定会有一条新的边连出去（讨论点）
    - 这个点一定不是起点或者以前走过的点，因为起点的度为 $1$ ，中间的点度为 $2$ ，度都用完了
    - 所以只能连向一个新的没有用过的点
  由于点数有限，所以不可能一直延申，一定会到达边界点结束
  所以不会有环，起点为边界，终点也为边界
- 从度为 $2$ 的内部点出发，一定可以存在一个相邻点可以走（讨论点）
  - 第 n 个内部点
    - 有可能连向起点，这样会形成简单环
    - 不可能连向中间的点
    - 可能连向个新的没有用过的点
  由于点数有限，所以不可能一直延申，所以最后会连向自己（因为排除了边界点）
  所以构成了若干个简单环
- 所以就是一个环图，直接用图的遍历即可

每个点最多遍历两遍，故复杂度 $O(4nm)$ ，暴力枚举每个路径即可，路径不会走到环里（因是环图，只有简单环），故不存在-1 情况

代码

python dfs 还是会爆栈

'''
Author: NEFU AB-IN
Date: 2022-01-20 00:31:57
FilePath: \ACM\Acwing\1929.py
LastEditTime: 2022-01-20 00:51:46
'''
g = []

dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]
#上右下左
'''
    0
  3< >1
    2
'''


def dfs(x, y, op):
    cnt = 0
    # 看这条路径最长能走多远
    while x >= 0 and x < n and y >= 0 and y < m:
        op = (op ^ 1) if g[x][y] == '/' else (op ^ 3)
        x += dx[op]
        y += dy[op]
        cnt += 1
    return cnt


if __name__ == "__main__":
    n, m = map(int, input().split())
    for _ in range(n):
        s = input()
        g.append(s)
    res = 0
    # 枚举所有边界点
    # 两个边界列
    for i in range(n):
        res = max(res, dfs(i, 0, 1))  #1 代表从左边往右进的
        res = max(res, dfs(i, m - 1, 3))  #3 代表从右边往左进的
    # 两个边界行
    for i in range(m):
        res = max(res, dfs(0, i, 2))  #2 代表从上面往下进的
        res = max(res, dfs(n - 1, i, 0))  #0 代表从下面往上进的
    print(res)

1929. 镜子田地

题意

思路

代码