「蓝桥杯题解」数字接龙

前言

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

题目链接

代码

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);
    }
}