镜子田地

题目

链接：1929. 镜子田地 - AcWing题库

农夫约翰在屋子外面放了一些旧镜子，他的奶牛们像往常一样调皮地偷走了它们！

奶牛们将镜子放置在了一个矩形田地中，该田地可被划分为 N×M 个方格区域。

在每个方格区域中，奶牛在其某对对角之间放置一个双面镜，因此，共有两种放法，一种为 / 放置（镜子连接方格左下角和右上角），另一种为 \ 放置（镜子连接方格左上角和右下角）。

一天晚上，奶牛贝茜将激光发射器带到了该田地中。

她站在田地外面，沿着田地的行或列水平或垂直照射光束，使光束反射一定数量的镜子。

由于镜子都是沿对角线摆放，因此经反射镜反射的水平光束最终将垂直传播，反之亦然。

贝茜想知道从田地之外射入的水平或垂直光束最多可以在田地中被反射多少次。

给定镜子田地的布局，请帮助贝茜计算这个数字。

代码

import java.util.*;


public class Main {
    static int n, m;
    static String[] s = new String[1010];
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};
    public static int bfs(int x, int y, int d)
    {
        if(x < 1 || x > n || y < 0 || y >= m)
            return 0;
        if(s[x].charAt(y) == '/')
            d ^= 3;
        else
            d ^= 1;
        return bfs(x + dx[d], y + dy[d], d) + 1;
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        n = inScanner.nextInt();
        m = inScanner.nextInt();
        int ans = 0;
        for(int i = 1; i <= n; i ++)
            s[i] = inScanner.next();
        inScanner.close();
        for(int i = 1; i <= n; i ++)
        {
            ans = Math.max(ans, bfs(i, 0, 3));
            ans = Math.max(ans, bfs(i, m - 1, 1));
        }
        for(int i = 0; i < m; i ++)
        {
            ans = Math.max(ans, bfs(1, i, 2));
            ans = Math.max(ans, bfs(n, i, 0));
        }
        System.out.println(ans);
    }
}
/*
3 3
/\\
\\\
/\/
*/