1. 问题引入当“铺瓷砖”遇上“去重”与“计数”最近在整理蓝桥杯国赛的历年真题翻到了第八届的这道“瓷砖样式”。题目本身描述很直观给你一个2行N列的网格用1x2的瓷砖可以横着放也可以竖着放去铺满要求计算所有不同的铺法总数。这里的“不同”指的是两种铺法不能通过旋转整个网格题目隐含了不能旋转因为网格是2行N列旋转后行列数互换形状变了或整体平移因为网格固定平移无意义得到相同的图案。换句话说我们要统计的是本质不同的瓷砖排列“样式”。初看这题很多人的第一反应是动态规划DP。确实对于“铺满棋盘”类问题DP是经典解法。对于2xN的网格用1x2的砖块状态转移方程可以很快写出来。但仔细读题你会发现坑点在于“不同样式”的判断。DP擅长计数“所有铺满的方案数”但它天然地不擅长处理“去重”——即识别两个方案是否只是瓷砖排列的“皮肤”不同但“骨骼”连通块、边界完全一致。题目要求的“样式”恰恰关注的是这种“皮肤”层面的差异。举个例子假设N3。一种铺法是第一行横着放一块砖覆盖(1,1)(1,2)第二行横着放一块砖覆盖(2,1)(2,2)然后两行剩下的(1,3)和(2,3)用一块竖砖覆盖。另一种铺法是第一行横着放(1,2)(1,3)第二行横着放(2,2)(2,3)然后(1,1)和(2,1)用竖砖覆盖。在DP眼里这是两种不同的状态转移路径会被计为两种方案。但在“样式”眼里如果把整个图案打印出来它们看起来是完全不同的两种图案吗不如果我们把第一种图案水平翻转一下就会得到第二种图案。题目是否允许这种翻转通常这类“样式”题如果不特别说明“旋转、翻转视为同一种”那么水平翻转产生的图案应该被视为一种新的样式因为瓷砖的“朝向”和“位置”信息发生了变化。但更常见也更严谨的做法是题目会明确说明“旋转或翻转后相同的算同一种”。本题虽然没有在简短描述中明说但从其考察意图和“样式”一词的普遍理解来看它很可能要求不考虑旋转和翻转的去重即只关心瓷砖在固定坐标系下的精确排列。然而这依然无法用简单的DP状态来区分因为DP的状态只记录了当前列的覆盖情况丢失了瓷砖的“身份”信息。这就引出了本题的核心难点如何高效地生成所有可能的铺法并对其“样式”进行唯一性判断暴力枚举所有瓷砖的摆放位置复杂度太高。这时DFS深度优先搜索结合“状态哈希”就成了一个非常自然的思路。但直接DFS整个网格每一步选择一块瓷砖放置分支太多且去重判断极其繁琐。我们需要一个更聪明的搜索策略这就是标题中提到的“中转点”思想。这个“中转点”在我看来是整个解题思路的枢纽它巧妙地将一个二维的铺砖问题转化为了一个对“缝隙”或“决策点”的一维搜索问题极大地缩小了搜索空间并使得样式编码和去重变得可行。2. 核心思路拆解从网格到“决策序列”的转化我们先抛开代码从逻辑上理解“中转点”是什么以及它如何工作。想象一下我们正在铺这个2xN的网格。我们从左到右一列一列地看。由于瓷砖是1x2的它的摆放只会有三种基本类型竖砖覆盖同一列的两行即覆盖(i, j)和(i1, j)。这里i1 j是列号。横砖在上行覆盖第一行的相邻两列即覆盖(1, j)和(1, j1)。横砖在下行覆盖第二行的相邻两列即覆盖(2, j)和(2, j1)。一个关键观察是当我们从左到右推进时每一列的两个格子其被覆盖的方式是有限的并且只与当前列和下一列有关。更进一步我们可以定义一个“决策点”。一个常见的“中转点”定义是每次决策都围绕一个特定的格子比如当前未覆盖的最左上角的格子来进行。但这种方法在去重时比较麻烦。另一种更高效、更适合编码去重的“中转点”定义是将网格的每个“位置”看作一个需要被覆盖的单元我们按照某种固定的顺序例如先行后列依次处理每个位置。如果当前位置已经被覆盖就跳过如果未被覆盖则尝试所有可能的瓷砖放置方式该瓷砖必须覆盖住这个“当前位置”。这个“当前位置”就是我们的“中转点”或“决策锚点”。它保证了我们生成铺法的过程是无重复且完备的完备性因为每个未覆盖的格子最终都会被某个瓷砖覆盖且我们总是从第一个未覆盖的格子开始尝试所以所有铺法都会被探索到。无重复生成由于我们固定了放置瓷砖的“起点”即第一个未覆盖的格子并且按照固定的顺序比如行优先、列优先去扫描下一个未覆盖点这就避免了因为放置顺序不同而生成相同的物理布局。例如先放A砖再放B砖和先放B砖再放A砖最终铺出来的瓷砖位置集合是一样的。我们的“锚点”顺序搜索法只会以“先处理A砖锚点后处理B砖锚点”这一种顺序生成该布局。但是这样生成的方案数量仍然是巨大的并且包含了大量“样式”相同的方案。因为同样的物理布局可能会因为我们在处理“锚点”时对于某个位置有多种合法的瓷砖放置方式比如可以放横砖也可以放竖砖如果空间允许而通过不同的搜索分支生成多次。实际上对于同一个物理布局只要其瓷砖集合相同我们的搜索算法可能通过不同的分支访问它多次。因此在搜索过程中或搜索结束后我们必须有一个“去重”机制来判断当前生成的这个瓷砖布局样式是否已经被计数过。这就引出了第二个关键点如何表示一个“样式”以便快速判断是否重复我们需要一个唯一的、与瓷砖放置顺序无关的编码来代表整个网格的铺砖状态。3. 状态编码与哈希去重将图案“指纹化”既然“中转点”搜索保证了我们能够生成各种铺法那么接下来的问题就是给每种铺法生成一个“身份证”用于去重。对于2行N列的网格一个直观的编码方式是使用一个二维数组grid[2][N]每个格子存储一个数字表示覆盖该格子的瓷砖的“编号”。同一块瓷砖覆盖的两个格子具有相同的编号。例如我们可以用DFS给每块新放置的瓷砖分配一个递增的ID。铺完后我们就得到了一个数字矩阵。这个矩阵唯一地标识了一种铺法。但是直接比较二维数组效率很低。我们需要将其转化为一个可以快速比较和存储的哈希值。一个经典且高效的做法是将二维数组状态压缩为一个字符串或一个长整数。按照行优先的顺序遍历整个grid。对于每个格子将其存储的瓷砖ID转化为一个字符如果ID小于10可以用数字字符如果更大可能需要用字母。将所有字符拼接起来形成一个长字符串。这个字符串就是这种铺法的“指纹”。只要铺法不同这个字符串几乎必然不同在ID分配规则固定的情况下。我们将这个字符串存入一个哈希集合如C的unordered_setstring或C的自行实现的哈希表中。每次搜索完成一种铺法即铺满所有格子就计算其指纹并尝试插入集合。如果插入成功说明是新的样式则计数器加1。这里有一个至关重要的细节瓷砖ID的分配必须与铺砖顺序无关只与瓷砖的物理位置相关。如果我们简单地在DFS过程中按放置顺序分配递增ID那么同一个物理布局因为放置顺序不同可能会产生不同的ID序列从而导致指纹字符串不同无法正确去重。为了解决这个问题我们需要一个更稳定的“瓷砖标识符”生成算法。一个可行的方法是在生成指纹字符串时不直接使用DFS分配的临时ID而是根据瓷砖覆盖的格子坐标动态计算一个唯一标识。例如可以取该瓷砖覆盖的所有格子中按行优先顺序最小的那个格子的坐标(r, c)将其转化为一个唯一数字idx r * N c作为这块瓷砖的ID。这样无论这块瓷砖在DFS中何时被放置只要它的位置固定其ID就是固定的。然后我们再根据这个规则重新扫描整个grid为每块瓷砖分配稳定的ID再生成指纹字符串。这个过程可以在DFS回溯到顶层、确认网格铺满时进行。另一种更巧妙的、无需二次扫描的方法是在DFS放置瓷砖时就采用一种“染色”策略使得同一块瓷砖的染色值在最终状态中是唯一的。但这通常更难实现。因此在搜索完成后进行一次“标准化”编码是更清晰可靠的做法。4. DFS搜索框架与“中转点”实现细节现在我们将“中转点”搜索和状态编码结合起来勾勒出DFS的框架。数据结构定义int grid[2][MAX_N]: 用于标记网格0表示未覆盖非0表示被某块瓷砖覆盖。初始时所有元素为0。unordered_setstring pattern_set: 用于存储所有出现过的样式指纹字符串。int count 0: 用于记录不同的样式数量。DFS函数设计函数原型可以设为void dfs(int pos)。 这里的pos是一个“线性化”的格子索引。假设我们按行优先顺序将2行N列的网格拉平为一维数组那么索引pos的范围是[0, 2*N-1]。pos就是我们寻找“第一个未覆盖格子”的当前位置。搜索逻辑寻找中转点决策锚点在dfs(pos)中我们不需要参数pos表示当前要决策的位置。更常见的写法是DFS函数不携带位置参数而是在函数内部用一个循环寻找当前网格中第一个值为0未覆盖的格子记其坐标为(r, c)。这个(r, c)就是本次DFS调用的“中转点”。如果找不到这样的格子说明网格已铺满进入步骤4。尝试放置竖砖如果r 0在第一行且grid[1][c] 0正下方的格子也空着那么可以放置一块竖砖。我们给这块砖分配一个临时标记比如一个全局递增的瓷砖ID仅用于本次DFS路径内的标记。将grid[r][c]和grid[r1][c]都标记为该ID。然后递归调用dfs()继续搜索。回溯时将这两个格子恢复为0。尝试放置横砖如果c N-1不是最后一列且grid[r][c1] 0右边的格子空着那么可以放置一块横砖。同样分配一个新的临时ID标记grid[r][c]和grid[r][c1]递归调用dfs()然后回溯。处理完整状态当发现网格中没有未覆盖的格子即grid全非0时说明找到了一种铺满的方案。此时我们需要生成该方案的“标准化指纹”。创建一个新的int stable_id[2][MAX_N]数组初始为0。遍历原grid对于每个非0的格子查看其代表的瓷砖。我们需要为每块物理瓷砖分配一个稳定的ID。可以采用这样的算法维护一个当前稳定ID值sid1和一个从(临时ID) - (稳定ID)的映射map。再次遍历grid行优先当遇到一个格子(i,j)其grid[i][j]的临时IDtid未被映射时执行map[tid] sid。然后将stable_id[i][j]设为map[tid]。如果tid已被映射则直接使用映射值。遍历结束后stable_id数组就包含了与放置顺序无关的、只与瓷砖位置相关的稳定编码。将这个stable_id数组按行优先顺序转化为一个字符串hash_key。将hash_key插入pattern_set。如果插入成功即之前没有这个样式则count。搜索起点调用dfs()从寻找第一个未覆盖格子开始。复杂度与优化这个搜索的复杂度是指数级的但对于蓝桥杯国赛的N通常N不会太大比如N10是可行的。我们可以进行一些优化比如在寻找“第一个未覆盖格子”时可以记录上一次找到的位置下次从这个位置开始找避免每次都从头扫描。5. 一个具体的例子与调试分析假设N3。我们手动推演一下DFS的过程重点关注“中转点”和去重。初始网格[0, 0, 0] [0, 0, 0]第一个未覆盖点是(0,0)。分支1在(0,0)放竖砖。 放置后状态假设临时ID为1[1, 0, 0] [1, 0, 0]下一个未覆盖点是(0,1)。分支1.1在(0,1)放横砖临时ID2。 状态[1, 2, 2] [1, 0, 0]下一个未覆盖点是(1,1)。只能放竖砖(临时ID3)。 最终状态[1, 2, 2] [1, 3, 3]铺满。生成稳定ID假设按行优先扫描第一块遇到的砖是竖砖(0,0)/(1,0)分配sid1。接着是横砖(0,1)/(0,2)分配sid2。最后是竖砖(1,1)/(1,2)分配sid3。指纹字符串“122133”。分支1.2在(0,1)放竖砖临时ID2。 状态[1, 2, 0] [1, 2, 0]下一个未覆盖点是(0,2)。可以放横砖覆盖(0,2)和(0,3)? 列越界不行。只能尝试和(1,2)放竖砖但(1,2)已经被覆盖了。实际上(0,2)的右边和下面都没有空位了这是一个死胡同。说明这个分支无法铺满。DFS会回溯。分支2在(0,0)放横砖临时ID1。 状态[1, 1, 0] [0, 0, 0]下一个未覆盖点是(1,0)。它可以和(1,1)放横砖或者和(0,0)下面的(1,0)放竖砖(0,0)已被覆盖所以只能尝试横砖或与(0,0)无关的竖砖。实际上(1,0)只能尝试与(1,1)放横砖或者与(0,0)放竖砖但(0,0)已占用无效。所以只能尝试横砖(1,0)/(1,1)临时ID2。 状态[1, 1, 0] [2, 2, 0]下一个未覆盖点是(0,2)。它只能和(1,2)放竖砖临时ID3。 最终状态[1, 1, 3] [2, 2, 3]铺满。生成稳定ID扫描顺序先遇到横砖(0,0)/(0,1) - sid1。然后横砖(1,0)/(1,1) - sid2。最后竖砖(0,2)/(1,2) - sid3。指纹字符串“113223”。我们可以看到通过这种方式我们得到了两种铺法并且它们的指纹字符串不同。如果还有其他铺法比如全部用竖砖也会被枚举并生成不同的指纹。在实际编程调试时有几个关键点需要验证死胡同判断DFS中当为一个“中转点”尝试所有合法放置方式后如果没有任何一种方式能成功放置函数应该直接返回不再继续寻找下一个未覆盖点。因为当前这个格子必须被覆盖如果无法覆盖说明之前的放置选择导致了无法铺满的状态需要回溯。临时ID管理临时ID必须在回溯时被“释放”或者使用一个在每次递归调用中递增的局部ID。通常使用一个全局变量tile_id在放置新瓷砖时tile_id回溯时无需特意递减因为下一次放置会覆盖这个ID值。只要保证同一路径上ID不重复即可。哈希集合的效率当N较大时样式数量会增长很快。使用unordered_setstring在C中通常是高效的。如果担心字符串哈希碰撞虽然概率极低可以在插入后检查count或者使用双哈希。对于竞赛题目unordered_set足够。内存与速度grid数组不要开得过大。DFS的递归深度最大为2*N对于N10深度20栈空间完全足够。6. 从解题到举一反三DFS“中转点”模型的通用性这道题的精髓不在于最终的答案是多少而在于“中转点”搜索结合“状态哈希去重”这一套组合拳。它解决了一类“枚举所有可能状态并去重”的问题。我们可以把这个模型抽象出来状态表示用一个数据结构如数组表示当前局面。决策锚点定义一种在未完成状态中选取下一个待决策单元的策略如“第一个未覆盖的格子”、“编号最小的未染色顶点”。这保证了生成路径的唯一性避免了因操作顺序不同导致的重复枚举。动作枚举在锚点处枚举所有合法的、能改变状态的动作如放置一块砖、给一个区域染色。状态转移与回溯执行动作更新状态递归进入下一层。返回后撤销动作回溯。终态判定与收集当达到终止条件如所有单元都被处理将当前状态转化为一个唯一标识符哈希值。去重存储将标识符存入集合实现去重。这个模型适用于许多组合枚举问题例如拼图问题用给定形状的拼块覆盖棋盘求所有不同拼法。图的着色方案计数给图的顶点着色相邻点颜色不同求所有本质不同的着色方案考虑颜色置换等价。多边形划分将一个多边形划分成三角形求所有不同的划分方式。在蓝桥杯等竞赛中遇到需要枚举“样式”、“布局”、“方案”并去重的题目如果数据范围允许通常状态空间在10^6量级以内都可以考虑这套DFS哈希的去重方案。它的优势在于思路直观代码相对容易实现和调试比纯数学推导或复杂的动态规划状态设计有时更不容易出错。7. 编码实现中的边界陷阱与性能调优在将上述思路转化为C/C代码时有几个细节需要特别注意它们往往是导致WA错误答案或TLE超时的罪魁祸首。陷阱一行列索引与数组范围题目是2行N列。在代码中我们通常用grid[0][j]和grid[1][j]表示第1行和第2行j从0到N-1。在尝试放置横砖时必须检查c1 N防止数组越界。在尝试放置竖砖时因为只有两行所以只需要检查r 0且grid[1][c]为空即可。这里的r是行索引0或1。陷阱二临时ID的分配与冲突如果我们使用一个全局整数next_id来分配临时ID并在每次放置新瓷砖时执行id next_id。这在一个DFS分支内是没问题的。但是当递归回溯后next_id的值并没有减少。下一次在新的分支中放置瓷砖时ID会继续递增。这会导致在整个搜索树中ID是单调递增的不同分支、不同位置的瓷砖ID可能相同也可能不同。这本身不影响搜索过程因为grid数组在回溯时被正确清空了。关键在于最后生成稳定指纹时不能直接使用这些临时ID。我们必须通过前面提到的“标准化”过程根据瓷砖的物理位置重新分配稳定的ID。如果错误地直接使用临时ID生成字符串必然导致去重失败。陷阱三哈希字符串的生成效率当N较大时比如N10网格有20个格子。生成指纹字符串需要遍历20个格子并将整数ID转化为字符。如果使用sprintf或to_string在循环中拼接效率较低。一个更高效的方法是预先分配一个足够长的字符数组如char key[41]20个格子每个格子最多两位ID加结束符然后使用snprintf一次性写入或者手动用数字计算哈希值例如将每块瓷砖的稳定ID视为一个数字使用多项式滚动哈希hash hash * BASE id。对于竞赛题目N10时样式总数不会过于庞大通常几千到几万直接使用std::string拼接通常也能通过。但养成优化意识是有益的。性能调优点尽早剪枝在DFS中如果发现剩余的空格子数量是奇数而瓷砖面积是偶数1x2显然无法铺满可以立即回溯。不过本题网格总格子数是2*N是偶数这个剪枝效果不大。更有效的剪枝是“未来检查”比如某一行连续的空格子数为奇数且无法通过跨行竖砖弥补也可以提前回溯但实现较复杂。优化“寻找第一个未覆盖点”不要每次都从(0,0)开始扫描。可以传递一个参数start给DFS表示从上一次找到未覆盖点的位置开始扫描。因为我们的放置顺序总是从左到右、从上到下未覆盖点的位置是单调不减的。使用更紧凑的状态表示对于2行N列我们可以用一个long long整数如果N31的位来表示每个格子是否被覆盖0/1用另一个同样长度的整数来存储瓷砖ID信息的一部分。但这需要更复杂的位操作且对于去重编码来说可能不如数组直观。在时间允许的情况下清晰性优先。对称性剪枝如果题目允许如果题目明确说明旋转、翻转后相同的算同一种那么我们在生成一种铺法后可以同时生成它的所有对称变换水平翻转、垂直翻转、旋转180度等并将这些变换的指纹也加入哈希集合或者只加入其中“最小”的一个作为代表。但这道题通常不考虑对称所以不需要。8. 总结与扩展思考回顾这道“瓷砖样式”题它的价值在于将一个看似是动态规划的问题通过“不同样式”这一要求引向了搜索与去重的领域。核心解题框架是DFS按序枚举放置 终态哈希去重。而“中转点”即按顺序处理第一个未覆盖格是保证DFS枚举不重不漏、且易于实现的关键策略。在实现层面最需要精细处理的是如何为最终铺满的网格生成一个与DFS探索顺序无关的唯一编码。我们采用了“二次扫描稳定ID分配”的方法虽然增加了一次O(N)的遍历但保证了去重的正确性逻辑清晰。对于想进一步挑战自己的同学可以思考以下变种如果网格是3行N列呢搜索空间会急剧增大可能需要结合状态压缩DP进行剪枝或者用更聪明的编码方式。如果瓷砖样式更多比如还有1x1的砖呢DFS框架依然适用只是在每个“中转点”需要枚举的动作种类增加了。如果要求输出具体的样式图案而不仅仅是计数呢那么我们可以在将指纹插入集合的同时将对应的grid状态或稳定ID数组也存储下来。最后在竞赛中遇到此类问题如果N的范围较小比如10DFS哈希通常是暴力但有效的保底解法。如果N更大就需要挖掘问题的数学规律或者设计更精巧的动态规划状态了。但无论如何理解并掌握这种“搜索去重”的范式对于解决许多组合计数问题都是大有裨益的。它锻炼的是一种将问题抽象为状态空间遍历并利用计算机的存储和计算能力进行穷举和筛选的思维能力这正是算法竞赛的核心魅力之一。