算法1
DFS
主要的点是把上下左右四种光线与“\”“/”这两种镜子对应起来一共有八种可能,然后就是照射后光线的变化以及下一道光线的路径变化的更新,这个用直接递归模拟DFS就很容易实现了,还有一点就是\为转意符号,这里输入时需要直接用一个字符串储存每行的数据再放在二维数组中
java代码
import java.util.Scanner;
public class Main {
//上0,下1,左2,右3
//0+\->2 2+\->0
//0+/->3 3+/->0
//1+\->3 3+\->1
//1+/->2 2+/->1
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(), M = sc.nextInt();
char[][] grid = new char[N][M];
for(int i = 0; i < N; i++) {
String temp = sc.next();
for(int j = 0; j < M; j++) {
grid[i][j] = temp.charAt(j);
}
}
int res = 0;
for(int i = 0; i < M; i++) {
res = Math.max(len(grid, 0, i, 1), res);
res = Math.max(len(grid, N - 1, i, 0), res);
}
for(int i = 0; i < N; i++) {
res = Math.max(len(grid, i, 0, 3), res);
res = Math.max(len(grid, i, M - 1, 2), res);
}
System.out.println(res);
}
public static int len(char[][] grid, int i, int j, int light) {
if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return 0;
switch (light) {
case 0:
if(grid[i][j] == '\\') return len(grid, i, j - 1, 2) + 1;
else return len(grid, i, j + 1, 3) + 1;
case 1:
if(grid[i][j] == '\\') return len(grid, i, j + 1, 3) + 1;
else return len(grid, i, j - 1, 2) + 1;
case 2:
if(grid[i][j] == '\\') return len(grid, i - 1, j, 0) + 1;
else return len(grid, i + 1, j, 1) + 1;
case 3:
if(grid[i][j] == '\\') return len(grid, i + 1, j, 1) + 1;
else return len(grid, i - 1, j, 0) + 1;
}
return 0;
}
}