前言

这个是我的 ac 代码，里面的注释是用自己的话写的。因为我看蓝桥杯官方题解文字和代码分离，代码部分没有注释，看着巨难受，所以自己写了一版。感觉他们的视频解析也挺水的（小声

题目链接

代码

java">import java.util.*;/*** 数字接龙*/public class Main {static Scanner in = new Scanner(System.in);static int n,k;static final int N = 11;static int[][] board = new int[N][N];static boolean[][] vis = new boolean[N][N];// 8*2 向量数组，其中下标 1 3 5 7 为对角线方向static int[][] d = {{-1,0},{-1,1},{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1}};static boolean[][][][] line = new boolean[N][N][N][N]; // 用来判断 (x1,y1) 是否可以沿对角线方向走到 (x2,y2)static void dfs(int x1,int y1,ArrayList<Integer> path) {// 终止条件：到右下角的那个格子if (x1 == n-1 && y1 == n-1) {// 没有把所有格子走完，不符题意if (path.size() != n*n - 1) return;// 输出路径for(int x : path) {System.out.print(x);}System.exit(0);}// 调试用的：System.out.println("(x1,y1): " + x1 + "," +y1);// ps：vis[x1][y1] = true;  加了这句就可以不用专门写 vis[0][0] = true// ps：因为我们是按 i 从小到大枚举的，所以如果存在答案，那么最先找到的那条路径肯定是字典序最小的for (int i = 0; i < 8; i++) {int x2 = x1 + d[i][0],y2 = y1 + d[i][1];// 判断边界以及是否访问过if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= n || vis[x2][y2]) continue;// 判断大小if ((board[x1][y1] + 1) % k != board[x2][y2] || line[x1][y1][x2][y2]) continue;// 沿对角线方向走，判断是否会交叉，这里四种情况（四个方向）只能分别老老实实写出来if(i == 1 && (line[x1 - 1][y1][x1][y1 + 1] || line[x1][y1 + 1][x1 - 1][y1])) continue ;if(i == 3 && (line[x1][y1 + 1][x1 + 1][y1] || line[x1 + 1][y1][x1][y1 + 1])) continue ;if(i == 5 && (line[x1][y1 - 1][x1 + 1][y1] || line[x1 + 1][y1][x1][y1 - 1])) continue ;if(i == 7 && (line[x1 - 1][y1][x1][y1 - 1] || line[x1][y1 - 1][x1 - 1][y1])) continue ;path.add(i);vis[x2][y2] = true;if (i % 2 == 1) line[x1][y1][x2][y2] = true;dfs(x2,y2,path);// 回溯path.remove(path.size()-1);vis[x2][y2] = false;if (i % 2 == 1) line[x1][y1][x2][y2] = false;}}public static void main(String[] args) {n = in.nextInt(); k = in.nextInt();for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {board[i][j] = in.nextInt();}}vis[0][0] = true;dfs(0,0,new ArrayList<>());System.out.println(-1);}
}