1. 问题引入从“玩具蛇”到深度优先搜索最近在整理历年国赛的算法题翻到了第十一届JAVA B组的这道“玩具蛇”。题目本身描述很简洁但背后考察的深度优先搜索思想却是一个让很多同学又爱又恨的经典考点。爱的是DFS的代码框架相对固定一旦掌握很多网格搜索、排列组合问题都能迎刃而恨的是细节处理不到位很容易陷入死循环、重复计数或者性能瓶颈的泥潭。这道“玩具蛇”题本质上就是一个在4x4的方格矩阵中寻找所有长度为16的、不重复路径的问题。你可以把它想象成一条长度为16节的小蛇要从某个起点出发一格一格地爬行直到填满整个16宫格期间不能走回头路也不能走出边界。我们的任务就是计算出从16个不同的起点出发一共能走出多少种不同的“满格”路径。这听起来是不是有点像小时候玩的“一笔画”游戏或者更准确地说是“哈密顿路径”问题在一个微小网格上的具体实例。对于算法新手来说直接面对“哈密顿路径”、“回溯”、“状态压缩”这些术语可能会有点发怵。别担心我们今天就用最直白的方式手把手拆解这道题不仅告诉你代码怎么写更重点剖析为什么这么写以及我在实现过程中踩过的那些坑。你会发现抛开那些唬人的名词DFS的核心思想其实非常直观和强大。2. 核心思路拆解为什么DFS是唯一正解面对一个4x4的网格要求找出一条遍历所有16个格点且不重复的路径我们的大脑可能会本能地尝试去“画”出几条。但稍微一试就会发现路径的数量可能远超想象。手动枚举那绝对是个不可能完成的任务。这时候我们就需要借助计算机的“暴力”计算能力而DFS正是执行这种系统性“试错”搜索的利器。2.1 问题建模把棋盘和蛇抽象成数据结构首先我们需要把问题翻译成计算机能理解的语言。棋盘Board一个4行4列的二维网格。我们可以用一个二维数组int[][] board new int[4][4]来表示。数组的每个元素初始值为0表示该格子未被蛇身占据。当蛇爬过一个格子我们就把该位置的值标记为1或者当前步数表示已被占用。蛇Snake在这里蛇不是一个独立的对象而是由一系列连续的、被标记的格子构成的路径。蛇的“状态”完全由棋盘上哪些格子被标记了即board数组的状态以及当前蛇头所在位置决定。移动Move蛇每一节只能从当前格子蛇头向上、下、左、右四个相邻的格子之一移动。这对应着坐标的变化(x-1, y),(x1, y),(x, y-1),(x, y1)。有了这个模型问题就转化为对于一个初始全为0的4x4棋盘从任意一个格子开始每次向四个方向之一移动如果目标格子未越界且未被访问值为0则标记它并继续移动。问当标记的格子总数达到16时这样的移动序列有多少种2.2 DFS与回溯的天然契合为什么DFS特别适合这个问题因为我们的搜索过程天然形成一棵“决策树”。树的根节点是搜索的起点即一个空的棋盘和蛇头的初始位置。树的分支在每个节点当前棋盘状态和蛇头位置我们有最多4个选择向四个方向移动。每个选择都会生成一个新的子节点新的棋盘状态和新的蛇头位置。树的叶子节点有两种。一种是“成功叶子”即棋盘上16个格子全部被标记我们找到了一条有效路径。另一种是“失败叶子”即当前蛇头无路可走所有相邻格子要么出界要么已被访问而棋盘还未满。DFS的策略就是从根节点开始沿着一条分支一个方向一直向下走深度优先直到到达叶子节点。如果到达成功叶子就计数加一如果到达失败叶子就原路返回回溯回到上一个节点尝试下一个分支另一个方向。“回溯”是这个过程中的关键动作。当我们从某个节点向下探索完所有子分支后我们需要撤销当前节点对全局状态造成的影响以便父节点能正确地探索其他分支。在这道题里“撤销”就是指将当前蛇头所在的格子从“已访问”状态重置回“未访问”状态并将蛇头位置回退到上一个位置。如果不做回溯状态就会混乱导致搜索错误。2.3 与BFS的对比为什么不用广度优先有些同学可能会想到广度优先搜索。BFS会逐层探索所有可能性。对于这个问题BFS在理论上是可行的但它会带来一个巨大的问题空间开销。在DFS中我们利用递归栈隐式地保存了从根节点到当前节点的路径。而在BFS中我们需要显式地使用队列来保存每一层所有的状态节点。一个“状态”需要包含整个4x4棋盘的信息16个格子和当前蛇头位置。即使进行状态压缩每个状态也需要一定的内存。在搜索树的中上层节点数量是指数级增长的。BFS需要在队列中同时保存大量中间状态对于16!量级可能性虽然实际远小于这个数的问题内存消耗将是灾难性的。而DFS在同一时刻只需要保存一条路径上的状态空间复杂度仅为O(N)其中N是路径长度这里是16优势非常明显。所以DFS回溯是解决此类“找出所有可能路径/排列”问题的标准且高效的武器。3. 代码实现逐行精讲理解了思路我们来看代码。下面是我用Java实现的一个版本我会加上详尽的注释并解释每一处设计的考量。public class ToySnake { // 定义方向数组上下左右。这是处理网格DFS移动的经典技巧。 static int[] dx {-1, 1, 0, 0}; static int[] dy {0, 0, -1, 1}; // 定义棋盘0表示未访问1表示已访问蛇身 static int[][] board new int[4][4]; // 用于记录最终结果 static int count 0; public static void main(String[] args) { // 遍历16个格子分别作为起点 for (int i 0; i 4; i) { for (int j 0; j 4; j) { // 每次开始新的起点搜索前必须重置棋盘 board new int[4][4]; // 标记起点 board[i][j] 1; // 从起点(i, j)开始深度搜索当前已走步数为1 dfs(i, j, 1); } } // 输出最终结果 System.out.println(count); } /** * 深度优先搜索函数 * param x 当前蛇头所在的横坐标 * param y 当前蛇头所在的纵坐标 * param step 当前已经走过的步数即蛇的长度 */ static void dfs(int x, int y, int step) { // 递归终止条件如果已经走了16步说明填满了棋盘 if (step 16) { count; // 找到一条有效路径 return; } // 遍历四个方向 for (int d 0; d 4; d) { // 计算下一个目标格子的坐标 int nextX x dx[d]; int nextY y dy[d]; // 条件判断1.不能越界 2.目标格子必须未被访问 if (nextX 0 nextX 4 nextY 0 nextY 4 board[nextX][nextY] 0) { // 做出选择标记目标格子为已访问 board[nextX][nextY] 1; // 递归进入下一层搜索步数加1 dfs(nextX, nextY, step 1); // 回溯撤销选择将目标格子恢复为未访问状态 board[nextX][nextY] 0; } } // 如果当前节点的所有方向都尝试完毕函数将自动返回回溯到上一层 } }3.1 关键代码段深度解析1. 方向数组dx, dy这是处理网格类DFS的“标配”。它把四个方向的坐标变化规律性地存储起来这样在循环中就可以用d索引来统一处理避免了写四遍冗长的if判断。代码更简洁也不容易出错。2. 全局变量board和count这里使用了静态变量是为了在递归函数中方便地修改和访问它们。在竞赛或算法题中这种写法很常见。但在大型工程中更推荐将状态封装在对象里作为参数传递以避免全局状态带来的副作用。对于这道题全局变量的简洁性是合适的。3.main函数中的循环与重置board new int[4][4];这行代码至关重要它保证了每个起点的搜索都是独立的。如果我们忘记重置棋盘那么上一个起点搜索留下的“已访问”标记会污染下一个起点的搜索空间导致结果完全错误。这是我第一次写类似题目时犯的典型错误。4. 递归函数dfs的参数设计(x, y)当前状态即蛇头位置。这是搜索进行下去的“坐标”。step当前路径长度。它有两个作用一是作为递归终止的条件step16二是隐含地记录了搜索深度防止无限递归。5. 递归终止条件if (step 16)是成功的终止。注意这里没有“失败”的显式终止条件。失败的情况是通过for循环中的if条件来控制的当当前节点所有可能的方向都不合法时for循环结束函数自然返回也就回溯到了上一层。这种写法很优雅。6. 回溯的精髓board[nextX][nextY] 1; // 做出选择 dfs(...); // 递归探索 board[nextX][nextY] 0; // 撤销选择这三行代码是回溯算法的模板。它像是一次“试探”先标记这个格子选择这条路然后派“侦察兵”递归调用深入敌后探索所有可能性。等“侦察兵”完成任务递归返回我们再擦掉标记撤销选择恢复现场以便尝试下一个方向。忘记写回溯语句是DFS出错的最主要原因之一会导致路径被重复使用结果比实际大很多。4. 性能优化与剪枝思考上面的代码已经可以正确运行并得到答案。在4x4的规模下它运行得很快。但如果我们把问题规模稍微扩大比如变成5x5朴素的DFS就会变得非常慢。这时我们就需要考虑“剪枝”——提前排除那些明显不可能到达终点的搜索分支减少不必要的计算。对于本题虽然不需要剪枝也能过但理解剪枝思想对提升算法能力至关重要。这里分享两个可以思考的优化点4.1 对称性剪枝本题特有效仔细观察4x4的棋盘它是一个正方形具有很高的对称性。从(0,0)点出发的路径数和从(0,3)、(3,0)、(3,3)这三个角点出发的路径数理论上应该是一样的因为棋盘可以通过旋转和翻折重合。同样四条边中间的点(0,1)和(1,0)等也应该具有对称性。一个激进的优化思路是我们只计算少数几个“代表点”的路径数然后乘以对称点的数量。例如只计算从(0,0)角点、(0,1)非角点的边点、(1,1)中心点出发的路径数然后分别乘以4、4、1中心点对称性不同再求和。但是这种优化需要非常严谨的数学证明确保对称性不被路径本身的方向性破坏。在竞赛中除非有绝对把握否则不建议轻易使用对称性剪枝因为容易算错。朴素的16起点搜索更为稳妥。4.2 连通性剪枝通用优化这是一个更通用、更安全的优化思路。想象一下在搜索过程中如果蛇的身体把棋盘上的空白区域分成了互不连通的两部分那么蛇无论如何也不可能不重复地走完所有格子了因为蛇是连续的身体无法“跳跃”。上图示意蛇身黑色将剩余空白格白色分成了两个不连通的区域。此时无论怎么走都无法访问所有白格。我们可以在DFS的每一步快速检查剩余空白格是否仍然是一个连通区域。如果不是就可以立即回溯不再继续搜索。这能剪掉大量无效分支。检查连通性可以用一次BFS或DFS来实现但这本身也有开销。对于小棋盘4x4增加连通性检查的开销可能抵消甚至超过它带来的收益属于“负优化”。但对于更大的棋盘如6x6这种剪枝会非常有效。提示在算法竞赛中“过早优化是万恶之源”。首先写出正确、清晰的朴素解法确保通过。如果时间超限再根据题目特点分析性能瓶颈有针对性地进行优化。对于这道国赛题朴素DFS完全足够。5. 调试与验证如何确保你的答案是对的写完代码跑出结果但你怎么知道这个数字对不对呢对于搜索类问题有几种验证思路小规模验证这是最有效的方法。你可以先把问题规模改小比如在2x2或3x3的棋盘上手动计算或运行程序将结果与手动枚举或逻辑推导的结果对比。例如2x2棋盘从任意角点出发只有2种走法顺时针或逆时针。用你的程序改一下尺寸跑一遍看结果是不是4起点 * 2 8。如果小规模对了大规模正确的概率就很高。输出中间状态在递归函数中当step达到16时不要只计数可以打印出当前棋盘的状态一种路径。观察几条打印的路径看它们是否符合规则连续、不重复、满格。这能帮你发现回溯逻辑的错误。逻辑检验检查你的计数是否包含了所有对称情况。例如因为起点有16个且棋盘完全对称最终结果应该是一个比较大的偶数。如果算出个奇数那肯定有问题。交叉验证如果可能用另一种思路写一个程序比如用BFS虽然慢但思路简单在小规模问题上验证结果是否一致。或者在网上寻找可靠的题解进行答案比对。对于这道题最终的正确结果是552。你可以用这个数字来验证你的程序。6. 常见“坑点”与实战心得回顾这道题和类似的DFS问题我总结了几条容易出错的地方和心得回溯的“配对”操作这是重中之重。每一个“做出选择”如board[x][y]1都必须有一个完全对应的“撤销选择”board[x][y]0在递归调用之后。而且要确保在递归的所有返回路径上包括通过return返回和函数自然结束返回撤销操作都能被执行到。上面的模板化写法是最安全的。状态重置当需要以多个不同起点独立搜索时一定记得为每个起点初始化全新的状态。就像我们main函数里对board的new操作。边界判断的顺序在判断下一个位置(nextX, nextY)是否合法时一定要先判断数组下标是否越界再判断该位置的状态。即nextX 0 nextX n的判断要放在board[nextX][nextY] 0之前。否则如果nextX已经越界程序会先尝试访问board[nextX][nextY]从而引发ArrayIndexOutOfBoundsException异常。递归深度本题路径长度是16递归深度也就是16对于JVM的栈空间来说完全没问题。但如果问题规模变大比如网格变成10x10递归深度达到100就需要警惕栈溢出的风险。这时可以考虑使用显式的栈Stack来模拟递归过程即迭代式的深度优先搜索。使用step避免额外空间我们直接用step计数而没有用一个List来存储路径。这是因为题目只要求计数不要求输出具体路径。如果要求输出所有路径就需要一个列表来记录每一步的坐标并在找到解时保存列表的副本。这会增加空间和时间开销。最后DFS回溯算法就像是在走一个巨大的迷宫并且要记录下每一条能走通的路。board数组就是你的“粉笔”用来标记走过的路递归调用就是你的“分身”去探索岔路而回溯时的board[nextX][nextY] 0就是你的“橡皮擦”把标记擦掉以便尝试其他岔路。理解了这个比喻你就能更好地把握这个算法的精髓。多练习几道类似的题目如“N皇后”、“全排列”、“岛屿数量”的变种你就能对DFS的应用场景和代码手感越来越熟悉。