1. 项目概述从“搭积木”到“状态压缩”的思维跃迁“蓝桥杯18年国赛 搭积木”这个标题乍一看像是少儿编程或趣味竞赛但如果你真这么想那可就掉进坑里了。作为一项国家级别的程序设计竞赛真题它早已脱离了简单的图形化拼接演变成一道考察动态规划与状态压缩思想的经典算法难题。这道题的核心是要求参赛者计算出在给定限制下用若干种特定形状的积木在题目中通常抽象为不同大小的矩形或特定图案填满一个指定区域的所有不同方案数。这听起来是不是有点像小时候玩的俄罗斯方块拼图但它的难度在于区域可能很大积木形状可能很怪直接枚举所有摆放方式在时间上是绝对不可能完成的。这正是蓝桥杯国赛题目的典型风格用一个生活化的场景包装一个深刻的计算机科学问题考察选手将实际问题抽象为数学模型并运用高效算法解决大规模计算的能力。对于正在备赛的选手或是希望提升自己动态规划DP功底的开发者来说吃透这道题意味着你掌握了解决一类组合计数与棋盘覆盖问题的通用钥匙。2. 问题本质与数学模型抽象2.1 题意解析与输入输出约定题目通常会给出一个高度为N、宽度为M的棋盘区域比如N2, M3以及若干种积木类型。每种积木用一个小的网格图表示例如1x2的横条、2x1的竖条、2x2的方块等。目标是用这些积木不重叠、不超出边界地铺满整个N*M的棋盘计算不同的铺法总数。积木可以旋转但通常不能翻转除非特别说明。输入就是N, M以及积木的形状描述输出是一个整数表示方案数。例如一个经典简化版是只有一种1x2的积木骨牌铺满2x3的棋盘有多少种方案这就是最简单的“多米诺骨牌覆盖”问题。而国赛题目的积木形状会更复杂可能包含L形、T形等使得问题直接跃升为NP-Hard类问题的简化版必须借助状态压缩动态规划来求解。2.2 核心挑战状态空间的爆炸最直观的想法是深度优先搜索DFS从左到右、从上到下尝试放置每一块积木。但这样做的复杂度是阶乘级的一旦棋盘尺寸超过6x6计算量就会变得无法承受。核心矛盾在于我们并不关心每块积木具体是哪一块只关心棋盘当前每一列的“填充状态”。因此我们需要一种方法来描述和转移这种“状态”。状态压缩动态规划状压DP正是为此而生。它的核心思想是用一个整数的二进制位来表示棋盘某一行的覆盖情况。通常我们用1表示该位置已经被积木占据0表示空位。对于高度为N的棋盘每一列的状态就可以用一个N位的二进制数来表示整个棋盘某一行的状态则是一个M位的二进制数但更常见的做法是按列递推。在“搭积木”问题中由于积木可能跨行我们通常选择按列递推状态表示当前处理到第几列以及当前列在受到上一列放置的积木影响后的“轮廓线”形状。2.3 状态定义与转移方程设计定义dp[col][state]表示当前处理到第col列并且从当前列开始向后看的若干列具体取决于积木的最大宽度的填充状态为state时的方案数。这里的state是一个二进制数它编码了当前列以及可能下一列的部分格子的占用情况。这是一种称为“轮廓线DP”或“插头DP”的经典技巧的简化形式。转移时我们需要枚举所有可能的方式在当前位置放置一块积木的左上角。放置积木需要检查积木形状是否与当前空白区域匹配即积木为1的位置state中对应的位必须为0。积木放置后不超出棋盘边界。积木放置后生成新的状态new_state。状态转移方程可以抽象为dp[col1][new_state] dp[col][state]从一个状态state通过放置某个积木转移到新的状态new_state。关键理解为什么状态要包含多列因为积木有宽度。当你放置一个宽度为2的积木时它不仅影响了当前列也影响了下一列。因此状态必须能表示出“当前列已放置、下一列部分被占用”的这种“承诺”以便在处理下一列时兑现。这是状压DP解决棋盘覆盖问题的精髓所在。3. 算法核心状态压缩DP的实战拆解3.1 积木的形状编码与预处理这是实现的第一步也是减少运行时计算量的关键。我们需要将每种积木的所有可能旋转形态都编码成计算机容易处理的形式。一个实用的方法是为每个积木定义一个“模具”mask。对于每个可能的放置位置左上角坐标(r, c)相对于当前处理点计算这个积木覆盖了哪些格子。我们可以用一个二元组(shift, mask)来表示一次放置shift: 积木覆盖的列偏移量。例如一个1x2的横条其shift1表示它影响到了下一列。mask: 一个二进制数表示在受影响的这几列内哪些格子被占据了。我们需要约定一个统一的顺序来映射格子到二进制位比如按行优先。实际操作中我们会预先计算出所有积木所有合法放置方式对应的(shift, mask)列表。在状态转移时直接遍历这个列表即可。# 示例定义1x2横条高度N2 # 假设状态是按列编码每列2位低位是第0行高位是第1行 # 初始状态state: 00 (两行都空) # 放置一个横条在左上角(0,0)它占据(0,0)和(0,1)格子。 # 对于第0列它占据了第0行 - mask位0置1。 # 它同时“承诺”了第1列的第0行也被占据。 # 因此这次放置可以表示为shift1, mask_on_col00b01, mask_on_col10b01。 # 但更通用的表示是一个跨越两列的mask。我们可以将状态扩展为表示连续几列的情况。 # 更常见的“轮廓线”做法是状态state表示当前列和下一列的部分情况。这里不展开复杂编码仅示意。 def generate_blocks(shape_grid, N): 根据积木的网格定义生成所有合法放置的(shift, full_mask)对。 shape_grid: 一个列表的列表表示积木形状1为有格子0为无。 N: 棋盘高度。 返回: list of (col_shift, mask) mask是一个长度为(col_shift1)的列表每个元素是对应列的占用位图。 blocks [] H, W len(shape_grid), len(shape_grid[0]) for rot in range(4): # 四种旋转 # 旋转形状... for start_r in range(N - H 1): for start_c in range(M - W 1): # 注意这里M是棋盘总宽在预处理时可能未知通常我们按相对位置处理 # 计算相对于放置点(0,0)的mask # 更通用的做法是不固定M计算相对偏移 pass return blocks由于棋盘宽度M在运行时才确定更常见的预处理是生成积木的“相对位置”集合。例如记录积木中每个格子相对于其左上角的(dr, dc)坐标。这样对于任意放置点(r, c)都能快速计算出覆盖了哪些(rdr, cdc)位置。3.2 状态转移的实现细节我们采用按列递推。设棋盘高度为N宽度为M。定义dp[col][state]其中state是一个二进制数它的长度是N * (K)这里K是一个关键表示状态需要记录当前列以及后续多少列的“承诺”。一个经典且易于实现的方法是使用轮廓线DP状态表示当前处理到棋盘的某个特定格子(i, j)以及从该格子开始向右、向下的轮廓线形状。但对于“搭积木”一种更直观的写法是“列状压DP”初始化dp[0][0] 1表示第0列之前没有列的状态是“全空”有1种方案。对于每一列c从0到M-1 a. 对于每个可能的状态s表示第c列及之后有限列的占用情况 b. 如果dp[c][s]为0跳过。 c. 尝试在当前列c的“最上方”的空位由状态s指示放置一个积木的左上角。 d. 放置时检查积木所有格子是否都在棋盘内且未被占用与状态s无冲突。 e. 放置后生成新的状态s。新状态需要清除当前列已填满的行并引入积木对后面列的“承诺”。 f. 将dp[c?][s]增加dp[c][s]。这里的列偏移?取决于积木的宽度。如果积木只占一列则转移到c1列如果占两列则可能仍然在c列但状态更新。这种方法在编码时状态s需要包含当前列和下一列的信息。一个常见的技巧是使用两个状态变量current_col_mask和next_col_mask。current_col_mask表示第c列的占用情况next_col_mask表示第c1列已做出的“承诺”占用情况。# 伪代码示例使用current_mask和next_mask dp [[0] * (1 N) for _ in range(M1)] # 简化版状态只表示单列占用 dp[0][0] 1 for col in range(M): for mask in range(1 N): if dp[col][mask] 0: continue # 找到当前mask中第一个为0的位第一个空行 # 这个循环是为了尝试在这个空位开始放置积木 for r in range(N): if not (mask (1 r)): # 第r行为空 # 尝试所有能放在(r, col)位置的积木 for block in blocks_at_position(r, col): # block 需要提供占用的行位图 this_col_mask以及对下一列的承诺 next_col_partial_mask if (mask this_col_mask) 0: # 不冲突 new_mask (mask | this_col_mask) N # 假设当前列填满后可以消去这里逻辑不完整仅为示意 # 更准确的是新的状态是下一列的初始状态它包含了之前next_mask和本次block的新承诺 next_mask ... # 计算新的next_mask dp[col1][next_mask] dp[col][mask]这只是一个高度简化的框架。完整的实现需要精心设计状态表示和转移函数以处理积木跨列的情况。3.3 复杂度分析与优化点假设棋盘高度N5状态用N位二进制表示单列则有2^N32种状态。这是可以接受的。但如果我们用状态表示两列用于处理宽度为2的积木状态数就是2^(2N)1024对于M100的棋盘DP数组大小约为100*1024转移时需要枚举当前状态和所有积木放置方式总体复杂度大约在O(M * 2^(2N) * B)其中B是平均每个位置可放置的积木种类数。在N5, M100的典型竞赛数据范围内这个复杂度是可行的。优化点预处理转移表对于每个状态s预先计算出所有可能的放置所得到的新状态s及其对应的积木放置。这样在DP主循环中只需遍历预计算好的列表避免了每次重复进行冲突检测和位运算能大幅提升速度。滚动数组由于dp[col]只依赖于dp[col-1]可以使用两个一维数组交替使用将空间复杂度从O(M * 2^N)降为O(2^N)。剪枝无效状态有些状态是无效的例如当前列的空位是孤立的上下都被占导致任何积木都无法放入。可以在预处理时排除这些状态减少遍历次数。利用对称性如果棋盘高度N较小很多状态是等价的。可以通过状态标准化如排序行来合并相同状态进一步减少状态空间。但这通常编码复杂度较高。4. 代码实现与关键步骤注释下面给出一个针对特定积木集合例如包含1x2, 2x1, 2x2的简化版实现框架。我们假设积木形状固定并且采用“当前列掩码下一列掩码”的双状态法。def solve_tiling(N, M, blocks): N: 棋盘高度 M: 棋盘宽度 blocks: 列表每个元素是一个元组 (dr_list, dc_list) 表示积木各格子相对于左上角的偏移 # 预处理所有可能的放置动作 (from_mask, to_mask, add_col) # from_mask 和 to_mask 都是 (current_col_mask, next_col_mask) 的编码 # 为了简化我们将两个mask编码成一个整数: state (next_mask N) | current_mask STATE_SIZE 1 (2 * N) # 状态总数实际很多状态无效 transitions [[] for _ in range(STATE_SIZE)] # 枚举所有可能的状态state (编码了cur_mask和next_mask) # 以及所有可能的放置位置(r)和积木(b) # 这是一个复杂的预处理循环核心是模拟放置并检查合法性生成新状态。 # 此处省略详细预处理代码因其较长且需精细的位操作。 # DP初始化 # 初始状态第0列之前当前列掩码为0全空下一列承诺也为0。 init_state 0 # (next_mask0, cur_mask0) dp [0] * STATE_SIZE dp[init_state] 1 for col in range(M): new_dp [0] * STATE_SIZE for s in range(STATE_SIZE): if dp[s] 0: continue cur_mask s ((1 N) - 1) next_mask s N # 如果当前列已经填满cur_mask的所有位都是1则可以转移到下一列的初始状态 if cur_mask (1 N) - 1: # 下一列的“当前掩码”就是之前承诺的next_mask new_s (0 N) | next_mask # 新的next_mask暂时为0 new_dp[new_s] dp[s] # 否则尝试在当前列的空位放置积木 else: # 找到第一个空位行r r 0 while cur_mask (1 r): r 1 # 尝试所有能放在(r, col)的积木 for block in blocks: # 检查这个积木能否放置所有格子(rdr, cdc)必须在棋盘内且未被占用 # 这里c是当前列需要检查cur_mask和next_mask ok True new_cur_mask cur_mask new_next_mask next_mask for dr, dc in block: nr r dr nc dc # 因为按列处理dc是列偏移0或1 if nr 0 or nr N: ok False break if nc 0: # 占用当前列 if new_cur_mask (1 nr): ok False break new_cur_mask | (1 nr) elif nc 1: # 占用下一列 if new_next_mask (1 nr): ok False break new_next_mask | (1 nr) else: # 积木宽度超过2本示例不支持 ok False break if ok: new_state (new_next_mask N) | new_cur_mask # 注意放置后并不立即跳到下一列状态更新后仍在当前列继续尝试放置 # 所以应该在同一列的状态间转移这里逻辑需要更精细的设计。 # 更标准的做法是预处理时生成的是“在当前状态下放置某积木后得到的新状态” # 然后DP时直接使用预处理的转移表。 new_dp[new_state] dp[s] dp new_dp # 最终状态处理完M列后当前列掩码为0因为最后一列也已处理完下一列承诺也为0。 final_state 0 return dp[final_state] # 定义积木1x2横条2x1竖条2x2方块 blocks [ [(0,0), (0,1)], # 1x2 横条 [(0,0), (1,0)], # 2x1 竖条 [(0,0), (0,1), (1,0), (1,1)], # 2x2 方块 ] # 注意这个blocks定义假设积木左上角在(0,0)并且列偏移dc只能是0或1。 # 实际编码中需要为每个积木生成所有旋转形态并确保dc非负且尽可能小。实现心路上面代码框架省略了最复杂的预处理部分因为它涉及大量位运算和状态枚举容易出错。在实际竞赛中我通常会先写一个DFS暴力搜索小规模数据如N3, M4来验证DP算法的正确性。生成所有状态转移时务必画图辅助明确每一位对应的棋盘格子。一个常见的错误是状态编码中行顺序弄反高位代表第0行还是第N-1行必须统一并贯穿始终。5. 调试技巧与常见问题排查即使理解了算法实现过程中也极易出错。以下是我在多次实现此类问题后总结的排查清单5.1 结果为0或明显偏小检查积木旋转是否遗漏了积木的某些旋转形态题目通常允许旋转你需要生成所有本质不同的旋转。例如一个2x3的积木旋转后可能变成3x2形状不同。检查状态初始化dp[0][初始状态]是否设为1初始状态是否正确代表了“第0列之前没有任何承诺”检查最终状态DP循环结束后你取结果的状态是否正确最终棋盘应被完全填满意味着最后一列处理完后不应再有对“下一列”的未兑现承诺。通常最终状态是(cur_mask 全满) (next_mask 0)或者经过若干列后cur_mask和next_mask都为0。检查转移条件在尝试放置积木时是否错误地要求当前列必须全空才能放实际上只要积木覆盖的格子与当前占用状态不冲突即可。整数溢出方案数可能非常大是否使用了long longC或Python的大整数蓝桥杯通常要求结果取模请仔细看题目输出要求。5.2 结果偏大或无限循环重复计数是否同一种铺法被计算了多次这通常发生在积木的“顺序”上。我们的DP状态定义了轮廓线按列推进本质上已经确定了放置的“顺序”从左到右每列内可能按行扫描因此不会重复计算不同的放置顺序。但如果积木种类相同需要确保DP过程不区分“第一块A积木”和“第二块A积木”即积木是无标号的。我们的算法通常默认积木无标号。状态转移死循环如果新状态又转移回自身且DP值不断增加就会爆掉。确保你的状态定义能推进“进度”。在按列扫描的模型中放置一个积木要么填满当前列某些行要么承诺了下一列最终必须推动“当前列”被填满从而进入下一列。5.3 性能问题超时无效状态过多预处理时没有过滤掉不可能出现的状态。例如next_mask对下一列的承诺中如果某行被承诺占用那么在下一列这一行就必须被占用。如果存在一个状态其cur_mask中某行是空的但next_mask中对应行却被承诺占用这可能是非法的因为到了下一列这个承诺无法由当前列的积木兑现因为当前列没放东西在那行。可以在预处理时剔除这些状态。转移枚举低效在DP主循环中嵌套了复杂的积木放置检查。务必使用预处理转移表。预先计算出从每个状态s出发所有合法的放置操作所到达的状态s。这样DP循环内就是简单的for s, val in dp.items(): for next_s in trans[s]: new_dp[next_s] val。使用字典而非数组当有效状态远小于总状态数时如2^(2N)使用字典Python的defaultdict或C的unordered_map来存储DP表可以节省大量空间和遍历时间。5.4 对拍验证策略对于这类计数问题最可靠的调试方法是“对拍”编写暴力DFS程序用于生成N和M很小比如N3, M4时的所有铺法并计数。这个程序逻辑简单容易写对。用DP程序跑同样的数据比较两个程序的结果。如果不一致打印出DP过程中每个状态的值或者让暴力程序输出所有铺法然后手动模拟DP过程看是哪里漏算或多算了。从小数据出发是调试算法问题的黄金法则。6. 从本题延伸的算法思维与训练建议“搭积木”这道题的价值远不止于解出这一道题。它为你打开了一扇门门后是一类广泛存在的“棋盘覆盖/铺砖问题”。掌握其核心——状态压缩DP你能解决许多变种变种1受限棋盘棋盘中有一些格子是坏的不能放置。只需在状态转移时额外判断积木覆盖的格子是否包含坏格即可。可以将坏格信息也编码进初始状态或作为转移的约束条件。变种2颜色覆盖积木有不同的颜色要求相邻积木颜色不同。这时状态需要额外记录最后一列或最后一个放置积木的颜色信息状态维度会增加。变种3三维积木问题升级到三维空间状态压缩可以从二维轮廓线扩展到三维表面轮廓状态表示和转移将更为复杂但思想一脉相承。要真正掌握我的建议是第一步彻底理解“多米诺骨牌覆盖1x2砖铺满MxN棋盘”的状压DP解法。这是最简单的入门。第二步动手实现蓝桥杯本题。尝试不同的积木组合如仅1x2 1x2和2x1混合加入L形积木。第三步在Online Judge上寻找类似题目练习如POJ 2411 (Mondriaans Dream) 是铺1x2和2x1砖的经典题。HDU 1400 (Mondriaans Dream) 同理。从这些经典题中巩固轮廓线DP的写法。第四步尝试解决更复杂的“插头DP”问题这类问题用于处理有连通性要求的路径覆盖是状压DP的进一步深化。最后一个很实在的心得在竞赛中遇到此类题如果时间紧张可以先用DFS暴力写出小数据范围的代码确保拿到部分分数。同时在草稿纸上清晰地画出状态编码图定义好dp数组的含义再开始编码。调试时print出前几列的状态转移表与手算的小规模样例对比是最高效的查错方法。状态压缩DP的代码往往“写起来费劲调起来更费劲”但一旦通过那种对问题建模和算法掌控带来的成就感是无与伦比的。