DFS中转点优化：从蓝桥杯瓷砖样式题看搜索效率提升

1. 项目概述：从一道经典国赛题看DFS的“中转点”优化

最近在复盘蓝桥杯历届真题，第八届国赛的“瓷砖样式”这道题让我印象尤为深刻。它初看是一道标准的深度优先搜索（DFS）回溯问题，但如果你只写出一个朴素的、按格子顺序填充的DFS，大概率会在比赛时限内得到“运行超时”的结果。这道题的精妙之处，也是它区分选手水平的关键，在于引入了一个被称为“中转点”或“跳跃点”的DFS搜索策略优化。今天，我就结合这道题，和大家深入聊聊这种优化思路的来龙去脉、具体实现，以及它如何将一道“暴力题”变成考验算法设计与剪枝艺术的典型。

简单来说，题目是这样的：有一个2行n列的墙面，我们需要用1x2（横着放）和2x1（竖着放）两种规格的瓷砖去铺满它。瓷砖有两种样式（比如颜色或花纹不同），铺好后，整个墙面不能有重复的图案（即两种铺法如果经过旋转、翻转后图案一致，则视为同一种）。最终需要计算有多少种不同的铺法。这里的核心挑战在于，n可以很大（题目中n=10），状态空间巨大，朴素的DFS逐个格子尝试放置瓷砖，其递归树会庞大到无法在时限内完成搜索。

2. 问题核心与朴素DFS的瓶颈分析

2.1 问题建模与状态定义

首先，我们需要将问题转化为计算机能处理的状态。墙面是2行n列，我们可以用一个二维数组grid[2][n]来表示，初始值均为0，表示该格子未被覆盖。1x2的瓷砖（横砖）会覆盖同一行相邻的两个格子；2x1的瓷砖（竖砖）会覆盖同一列上下两个格子。为了区分样式，我们可以用数字1和2来标记两种不同样式的瓷砖。

一个朴素的DFS思路非常直观：从墙面的左上角(0,0)开始，从左到右、从上到下扫描每个格子。

1. 如果当前格子(i, j)已经被覆盖，则跳到下一个格子。
2. 如果未被覆盖，则尝试两种瓷砖和两种样式：
   • 尝试放置竖砖：如果i=0（在第一行）且下方格子(1, j)未被覆盖，则可以用一块样式为c(c=1或2)的竖砖覆盖(i, j)和(1, j)。
   • 尝试放置横砖：如果j < n-1（不在最后一列）且右侧格子(i, j+1)未被覆盖，则可以用一块样式为c的横砖覆盖(i, j)和(i, j+1)。
3. 放置后，递归进入下一个格子（通常是(i, j+1)，注意处理行末换行）。
4. 回溯时，撤销瓷砖的放置。

当扫描完所有格子（即所有格子都被覆盖），我们就得到了一种完整的铺法。最后，需要对这些铺法进行去重，因为题目要求旋转、翻转后相同的视为同一种。

2.2 朴素DFS的性能瓶颈

这个思路正确，但效率极低。为什么？关键在于搜索顺序。

在朴素的“顺序扫描”DFS中，递归的深度是O(n)级别（因为每次处理一个格子或一对格子），这看起来不深。但是，它的分支因子非常大。在早期，尤其是在墙面还空着的时候，对于一个未覆盖的格子，我们最多有4种选择（竖砖样式1、竖砖样式2、横砖样式1、横砖样式2）。随着搜索的进行，选择会变少，但整个递归树依然庞大得惊人。

更致命的是，这种扫描方式会产生大量无效的中间状态和重复的搜索路径。例如，当我们在某个位置选择放置一块横砖时，它覆盖了两个格子，我们跳到下一个未覆盖的格子。但整个搜索进程是被“当前扫描坐标”这个单一变量驱动的，它无法智能地跳过那些已经被覆盖的、无需再次决策的区域，递归调用中仍然需要判断if (grid[i][j] != 0)。

对于n=10的情况，粗略估算状态数是一个天文数字，直接暴力搜索是不可行的。这就需要我们引入更高效的搜索策略——“中转点”优化。

3. “中转点”优化策略深度解析

“中转点”（或称“跳跃点”、“下一个未覆盖点”）优化是解决这类棋盘覆盖、骨牌铺砖问题的经典技巧。其核心思想是：改变DFS的驱动方式，不再按固定的行列顺序扫描，而是每次都直接定位到当前状态下第一个（或某个）未被覆盖的格子，从这个点开始尝试放置。

3.1 优化原理与优势

1. 消除无效递归：在朴素方法中，即使(i, j)已经被覆盖，我们还是会递归调用dfs(i, j+1)，这个调用进去后立刻因为grid[i][j]!=0而返回，做了无用功。通过直接寻找未覆盖点，我们确保每一次递归调用都是针对一个确实需要做出放置决策的格子，大幅减少了递归调用的次数。
2. 统一搜索入口：无论我们上次在哪里放置了瓷砖，下一次都从一个明确的“未覆盖点”开始。这使得递归函数的逻辑更清晰：它的任务就是“把从当前未覆盖点开始的剩余墙面铺满”。
3. 自然剪枝：在寻找未覆盖点的过程中，如果发现找不到（即所有格子都已覆盖），那么这就是一个合法的终点状态。这个判断逻辑被整合到了递归入口处。

3.2 具体实现方案

我们需要一个函数来找到当前墙面状态下的第一个未覆盖点。通常，我们可以用两个循环，或者更高效地，在递归函数调用时传入一个“起始查找索引”，然后线性扫描找到第一个grid[i][j] == 0的点(x, y)。

递归函数的签名会发生变化：

void dfs(int pos) { // 从索引pos开始，找到第一个未覆盖的格子(x,y) int x = -1, y = -1; for (int k = pos; k < 2 * n; ++k) { // 将二维坐标线性化 int i = k / n; int j = k % n; if (grid[i][j] == 0) { x = i; y = j; break; } } // 如果找不到未覆盖点，说明铺满了，记录方案 if (x == -1) { recordSolution(); return; } // 否则，在(x,y)尝试放置瓷砖 // ... 尝试放置竖砖和横砖 ... }

这里pos是线性化后的索引，初始为0。每次递归调用时，传入的pos参数就是当前找到的未覆盖点(x,y)对应的线性索引k。这样，下一次递归会从k+1开始查找，避免了重复扫描已经处理过的区域。

注意：线性化索引k = i * n + j是一种常见技巧，方便用一个变量表示二维坐标。在寻找下一个未覆盖点时，从pos开始扫描，而不是从头开始，这是效率提升的关键。

3.3 为何能大幅提升效率？

假设在某个中间状态，墙面大部分已被覆盖，只剩下角落一小块区域是空的。朴素DFS仍然会固执地从(0,0)开始，逐个格子判断是否被覆盖，经历大量立即返回的递归调用，才能走到真正的决策点。而“中转点”DFS通过一次O(n)的扫描（最坏情况），直接“空降”到决策点，中间的无效路径全部被跳过。

对于n=10，墙面积只有20个格子，每次寻找未覆盖点的成本最多是20次判断。而朴素DFS产生的递归树节点数量可能是百万甚至千万级别。此消彼长，“中转点”优化带来的效率提升是指数级的，使得搜索n=10成为可能。

4. 完整解题步骤与代码实现详解

理解了“中转点”思想，我们来看完整的解题步骤，包括去重。

4.1 步骤一：状态表示与初始化

我们使用一个二维数组int grid[2][N](N=10) 表示墙面。0表示空，1和2表示两种样式的瓷砖。我们需要一个全局变量ans来计数，以及一个数据结构（如set<string>）来存储和去重最终方案。

4.2 步骤二：实现带“中转点”的DFS函数

这是核心函数。我们按线性索引k来查找和传递位置。

#include <iostream> #include <set> #include <string> using namespace std; const int N = 10; int grid[2][N]; // 0-空，1-样式1，2-样式2 set<string> patterns; // 用于去重 int n = 10; // 列数 // 将当前网格状态编码成一个字符串，用于去重 string encode() { string s; for (int i = 0; i < 2; ++i) { for (int j = 0; j < n; ++j) { s += char('0' + grid[i][j]); } } return s; } void dfs(int start) { int x = -1, y = -1; // 寻找从start开始的第一个未覆盖点 for (int k = start; k < 2 * n; ++k) { int i = k / n; int j = k % n; if (grid[i][j] == 0) { x = i; y = j; break; } } // 如果所有格子都被覆盖，记录方案 if (x == -1) { patterns.insert(encode()); return; } // 尝试放置竖砖 (2x1) if (x == 0 && grid[1][y] == 0) { // 竖砖只能从第一行开始放 for (int c = 1; c <= 2; ++c) { // 两种样式 grid[x][y] = grid[x+1][y] = c; dfs(start); // 注意：放置后，(x,y)被覆盖，下一个未覆盖点可能就在当前k之后，所以可以传start，让查找过程自己推进。更精确的可以传 k+1。 grid[x][y] = grid[x+1][y] = 0; // 回溯 } } // 尝试放置横砖 (1x2) if (y + 1 < n && grid[x][y+1] == 0) { for (int c = 1; c <= 2; ++c) { grid[x][y] = grid[x][y+1] = c; dfs(start); grid[x][y] = grid[x][y+1] = 0; } } // 注意：这里没有“不放”的选择，因为我们必须铺满所有格子。 }

关键点讨论：在递归调用dfs(start)时，为什么传start而不是k+1？实际上，两种方式都可以，但传start更简单。因为我们在函数开头会从start开始线性扫描找到第一个空位(x,y)，其索引为k。无论我们传入的是start还是k，下一次扫描都会从传入的参数开始。如果我们放置了瓷砖，当前k位置被覆盖了，那么从start（它小于等于k）开始扫描，会跳过k（因为它现在非0了），找到下一个空位。这逻辑是成立的。但更精确和高效的做法是传入k+1，表示“从当前处理位置的下一个开始找”，可以减少一些扫描。不过在这个问题规模下，差异不大。为了逻辑清晰，代码中使用了start。

4.3 步骤三：去重处理

题目要求旋转、翻转后相同的视为同一种。对于一个2行n列的网格，其对称操作包括：

1. 水平翻转：上下两行交换。
2. 旋转180度：对于2xn矩阵，旋转180度等价于先水平翻转，再垂直翻转（即顺序交换），但最终效果可以归结为一种特定的映射。

一个稳妥的去重方法是：每当找到一个完整铺法（编码为字符串s），我们生成它所有可能的同构形式，将这些形式中的“最小表示”（如字典序最小的字符串）作为该方案的代表，存入set中。这样，本质上相同的方案只会被记录一次。

生成同构形式的函数可能如下：

string normalize(string s) { // s 是 2*n 长度的字符串，前n个是第0行，后n个是第1行 string minStr = s; string other; // 1. 原样 // minStr already holds s // 2. 水平翻转 (上下行交换) other = s.substr(n, n) + s.substr(0, n); if (other < minStr) minStr = other; // 对于2xn，旋转180度等价于字符串完全逆序？不对。 // 旋转180度： grid[i][j] -> grid[1-i][n-1-j] // 我们需要根据这个映射重新构造字符串 // 为了简化，有时题目会说明“只考虑平面本身的重复”，这时可能只需要考虑水平翻转。 // 在蓝桥杯本题的官方讨论中，通常认为需要去重的是“旋转和翻转”，但2行矩阵的旋转可能产生新的状态。 // 一个更全面的处理： // 我们有一个2xn的矩阵M。它的对称操作（保持矩形形状的）包括： // - 恒等变换 // - 水平翻转（上下翻转）：行交换 // - 垂直翻转（左右翻转）：每行反转 // - 旋转180度：水平翻转+垂直翻转 // 我们需要考虑这4种情况（实际上，对于长方形，其对称群是二阶二面体群，有4个元素）。 // 生成垂直翻转 string row0 = s.substr(0, n); string row1 = s.substr(n, n); reverse(row0.begin(), row0.end()); reverse(row1.begin(), row1.end()); other = row0 + row1; if (other < minStr) minStr = other; // 生成旋转180度 (水平翻转+垂直翻转，顺序无关) string h_flip = s.substr(n, n) + s.substr(0, n); // 水平翻转后的字符串 row0 = h_flip.substr(0, n); row1 = h_flip.substr(n, n); reverse(row0.begin(), row0.end()); reverse(row1.begin(), row1.end()); other = row0 + row1; if (other < minStr) minStr = other; return minStr; }

然后在dfs的终点，不再直接插入encode()的结果，而是插入normalize(encode())。

4.4 步骤四：主函数与结果

int main() { // 初始化网格为0 for (int i = 0; i < 2; ++i) { for (int j = 0; j < n; ++j) { grid[i][j] = 0; } } patterns.clear(); dfs(0); // 从线性索引0开始搜索 cout << patterns.size() << endl; return 0; }

运行上述代码（需要正确的去重函数），最终可以得到题目要求的答案。需要注意的是，由于去重逻辑的细微差别（是否考虑垂直翻转、旋转180度），最终答案可能略有不同，但核心的DFS搜索框架和“中转点”优化是不变的。

5. 关键细节、调试技巧与常见问题

5.1 线性索引与二维坐标的转换

这是实现“中转点”搜索的基础。务必确保转换公式正确：

• k = i * n + j
• i = k / n
• j = k % n在循环中，k的范围是[0, 2*n)。当n是常量时，这个计算很快。

5.2 递归参数的选择与优化

如前所述，递归参数传递start或k+1均可。我建议在初期使用start以保证逻辑简单正确，在确保搜索正确性后，可以优化为传递k+1以获得微小的性能提升。调试时，可以在递归入口打印start,x,y，观察搜索路径是否符合预期，是否跳过了已覆盖的格子。

5.3 样式尝试的顺序与剪枝

在尝试放置瓷砖时，我们循环了两种样式c=1和c=2。这里没有顺序要求，但保持一种固定顺序有助于结果的可复现性。这里没有额外的对称性剪枝，因为样式本身是题目要求区分的。如果题目不区分样式，那么在同一位置放置不同“颜色”的砖块是等价的，此时就需要剪枝，例如规定某种颜色优先，避免重复搜索对称状态。

5.4 去重逻辑的陷阱

这是本题最容易出错的地方。务必仔细理解题目中“重复”的定义。

• 仅水平翻转：很多人的第一反应是上下两行交换。对于2行的棋盘，这确实是主要的对称操作。
• 垂直翻转与旋转：一个2xn的图案，左右翻转（垂直翻转）和旋转180度后，可能会得到一个新的图案，这个图案可能不在我们原始的“水平翻转”集合里。是否需要考虑这些，取决于题目描述。在蓝桥杯的判题环境中，通常需要最严格意义上的去重，即考虑矩形的所有对称操作（共4种）。最稳妥的方法是，在无法确定时，实现所有可能的对称变换（恒等、水平翻转、垂直翻转、旋转180度），取所有变换结果中的最小表示（如字典序最小）作为唯一标识。

实操心得：在编写去重函数normalize()时，建议单独编写测试函数。手动构造几个小的、已知的铺法（例如n=2或3），计算它们的所有对称形式，检查你的normalize函数是否能为这些本质上相同的方案生成同一个代表字符串。这是验证去重逻辑正确性的有效方法。

5.5 性能分析与预估

对于n=10，使用“中转点”优化的DFS，其递归树的深度和宽度都被有效控制。尽管最坏情况下的理论复杂度仍然很高，但由于墙面积小（仅20格），且搜索过程中不断有格子被覆盖，分支因子迅速减小，实际可探索的完整状态数在可接受范围内（最终答案是一个具体的数字，大约在万的数量级）。在普通的个人计算机上，正确的实现可以在数秒到数十秒内完成计算。

如果时间仍然紧张，可以考虑进一步的优化，例如：

• 状态压缩：用两个整数的二进制位来表示每行的覆盖情况，可以加速状态判断和存储。
• 记忆化搜索（DP）：对于这种铺砖问题，有时可以用基于轮廓线的动态规划来解决，效率更高。但DFS+中转点的方法对于此题规模已经足够，且更直观。

5.6 常见错误排查清单

1. 死循环或栈溢出：检查递归终止条件。确保当找不到未覆盖点(x==-1)时，一定要return。
2. 结果为0或远小于预期：检查瓷砖放置的条件判断。确保竖砖放置时检查了x==0（或x<1）和grid[1][y]==0；横砖放置时检查了y+1 < n和grid[x][y+1]==0。同时，检查样式循环for (int c=1; c<=2; ++c)是否正确。
3. 结果远大于预期：这几乎肯定是去重逻辑出了问题。首先，尝试不加任何去重，计算原始方案总数。这个数字会非常大。然后逐步加入去重逻辑（先加水平翻转，再加垂直翻转等），观察结果变化，定位是哪种对称操作没有考虑到。
4. 运行超时：首先确认是否使用了“中转点”优化。如果使用了还超时，可能是去重操作normalize()和set.insert()过于耗时。确保encode()函数只在全盘铺满时调用一次，而不是在递归过程中频繁调用。normalize()函数也只对最终方案调用。

这道“瓷砖样式”题，从一个看似简单的铺砖问题，引申出了DFS搜索策略的重要优化技巧。掌握“中转点”思想，不仅能解决这道题，更能帮你打通任督二脉，应对一系列类似的“棋盘覆盖”、“状态搜索”问题。下次遇到需要铺满某种区域的题目，别再老老实实按顺序扫描了，想想能不能直接“空降”到下一个决策点，效率的提升会让你惊喜。