题目解析:1.不可以无限反射:因为我们开始都是从边界开始,光路可逆,所以一定可以返回到开始进入的地方。所以不会存在无限反射的情况
2.分析反射情况:
上(0)下(1)左(2)右(3)
2.1当镜子”"时
上(0)00 -> (当前镜子反射的方向)右(3)11 -> (下一面镜子接收的方向)左(2)10
右(3)11 -> (当前镜子反射的方向)上(0)00 -> (下一面镜子接收的方向)下(1)01
下(1)01 -> (当前镜子反射的方向)左(2)10 -> (下一面镜子接收的方向)右(3)11
左(2)10 -> (当前镜子反射的方向)下(1)01 -> (下一面镜子接收的方向)上(0)00
综上规律的出: 每个数和11进行异或运算即可得到下一步走的方向,每个数和01异或后可以得到下一面镜子接受的方向
当镜子”/”时:
上(0)00 -> (当前镜子反射的方向)左(2)10 -> (下一面镜子接收的方向)右(3)11
左(2)10 -> (当前镜子反射的方向)上(0)00 -> (下一面镜子接收的方向)下(1)01
下(1)01 -> (当前镜子反射的方向)右(3)11 -> (下一面镜子接收的方向)左(2)10
右(3)11 -> (当前镜子反射的方向)下(1)01 -> (下一面镜子接收的方向)上(0)00
综上规律的出: 每个数和10进行异或运算即可得到下一步走的方向,每个数和01异或后可以得到下一面镜子接受的方向
思路:dfs遍历每一条路径,
2.每条个镜子的每个结点能走到的地方一定是确定的
参考文献
https://www.acwing.com/solution/content/85002/
https://www.acwing.com/solution/content/85093/
https://www.acwing.com/solution/content/85067/
java 代码
import java.util.Scanner;
public class Main {
static int ans = 0;
static final int[][] d ={
{-1,0},//上
{1,0},//下
{0,-1},//左
{0,1}//右
};
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt();
int M = input.nextInt();
input.nextLine();
char[][] mirror = new char[N][M];
for (int i = 0; i < N; i++) {
String s = input.nextLine();
for (int j = 0; j < s.length(); j++) {
mirror[i][j] = s.charAt(j);
}
}
//2.用户输入完成,遍历农场的上下左右照射镜子
//2.1遍历上下方向的镜子
for (int i = 0; i < M; i++) {
dfs(mirror,0,0,i,1);//上
dfs(mirror,1,N-1,i,1);//下
}
for (int i = 0; i < N; i++) {
dfs(mirror,2,i,0,1);//左
dfs(mirror,3,i,M-1,1);//右
}
//3.输出结果
System.out.println(ans);
}
//光照射到镜子后走的方向
static void dfs(char[][] mirror,int direction,int x,int y,int count){
//1.记录走的最远的距离
ans = Math.max(ans,count);
//2.光向下一步走的地方
int nx = 0,ny = 0;
if (mirror[x][y] == '/'){
direction ^= 2;//10
}else {
direction ^= 3;//11
}
nx = x + d[direction][0];
ny = y + d[direction][1];
//3.如果下一个位置任然在规定的为直里,那么继续进行递归
if (nx>=0 && nx< mirror.length && ny>=0 && ny<mirror[nx].length){
dfs(mirror, direction^=01, nx, ny, count+1);
}
}
}