第十一届蓝桥杯JavaB组 试题E：玩具蛇（题目+题解）

问题描述

小蓝有一条玩具蛇，一共有16节，上面标着数字1至16。每一节都是一个正方形的形状。相邻的两节可以成直线或者成90 度角。

小蓝还有一个4×4的方格盒子，用于存放玩具蛇，盒子的方格上依次标着字母A到P共16个字母。

小蓝可以折叠自己的玩具蛇放到盒子里面。他发现，有很多种方案可以将玩具蛇放进去。

下图给出了两种方案:

请帮小蓝计算一下，总共有多少种不同的方案。如果两个方案中，存在玩具蛇的某一节放在了盒子的不同格子里，则认为是不同的方案。

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

类似于第八届蓝桥杯省赛C++ B组方格分割那道题，用DFS解决。我在写的时候，在写chech函数后，不满足check直接写了return导致后续结点无法访问，还有就是初始结点在main函数里也需要初始化，不然得出的不准

答案

552

代码

package Eleven;

import java.util.Stack;

public class T5 {
    public static void main(String[] args) {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                flags[i][j] = true;
                dfs(i, j,0);
                flags[i][j] = false;
            }
        }
        System.out.println(count);
    }
    static int count = 0;
    static int[][] maze = new int[4][4];
    static boolean[][] flags = new boolean[maze.length][maze[0].length];
    static int[][] sp = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};
    static Stack res = new Stack();

    private static boolean dfs(int i, int j,int index) {
        if (index == 15) {
            System.out.println(res);
            count++;
            return true;
        } else {
            for (int k = 0; k < 4; k++) {
                int x = i + sp[k][0];
                int y = j + sp[k][1];
                if (check(x, y)) {
                    flags[x][y] = true;
                    res.add("(" + x + "," + y + ")");
                    dfs(x, y,index+1);
                    flags[x][y] = false;
                    res.pop();

                } else {
                    continue;
                }
            }
            return false;
        }
   }
    private static boolean check(int i, int j) {
        return i >= 0 && i < maze.length && j >= 0 && j < maze[0].length && flags[i][j] == false;
    }
}