1. 项目概述与问题引入
“铺瓷砖”这个题目，听起来像是装修工地的活儿，但在算法竞赛的语境下，尤其是像蓝桥杯国赛这个级别的舞台上，它往往是一个披着生活外衣的、对动态规划（DP）和状态压缩技巧的深度考察。我当年第一次在模拟赛里遇到这类题目时，第一反应也是“这不就是排列组合吗？”，结果一上手就发现，状态空间大得惊人，暴力搜索根本跑不完。这类问题的核心魅力在于，它用一个非常直观的场景——用固定形状的瓷砖铺满一个给定大小的矩形地面——来包装一个复杂的组合数学与状态转移问题。对于Java B组的选手而言，这不仅是编程能力的测试，更是对思维严谨性、对问题抽象能力，以及对经典算法模型灵活运用的一次综合大考。
简单来说，题目通常会给你一个N x M的网格地面，以及一种或几种固定形状的瓷砖（比如1x2的长方形砖，或者更复杂的L形砖）。你需要计算出，恰好铺满整个地面（不允许重叠，不允许超出边界）的所有不同铺设方案数。这个“所有不同方案数”就是最终的答案，往往是一个巨大的数字，需要我们对结果取模。问题的难点从来不在于理解“铺满”这个概念，而在于如何高效、无遗漏且不重复地枚举所有可能的铺设状态。当N和M稍微大一点（比如达到10这个量级），朴素的想法（如深度优先搜索DFS）会立刻遇到组合爆炸，时间复杂度过高。这时，状态压缩动态规划（状压DP）就成了几乎唯一的“标准答案”。
在接下来的内容里，我不会仅仅给出一个AC的代码模板。那样做意义不大，因为下次题目稍微变一下形你可能又不会了。我将带你彻底拆解“铺瓷砖”问题的内核，从最基础的思路开始，一步步推导为什么需要状压DP，如何设计状态，如何进行状态转移，并针对Java实现中的关键细节和常见“坑点”进行重点剖析。我们会用1x2的砖块（即骨牌）覆盖N x M棋盘这个最经典的“多米诺骨牌覆盖”问题作为主线，因为它涵盖了此类问题的所有核心思想。掌握了它，再遇到L形砖、更复杂的棋盘（如存在障碍物）等变种，你都能触类旁通。
2. 从暴力搜索到状压DP：思路的演进与必然性
我们先从一个最直观的解法开始：深度优先搜索（DFS）。想象我们站在棋盘的左上角，尝试放置第一块砖。砖可以横着放（覆盖两个水平相邻的格子），也可以竖着放（覆盖两个垂直相邻的格子）。我们做一个选择，标记这两个格子为已覆盖，然后递归地去铺剩下的格子。当所有格子都被覆盖时，就找到了一种方案。
这个思路完全正确，但为什么不行呢？核心在于重复计算和状态爆炸。假设棋盘是2 x 3的，用1x2的砖去铺。我们手动枚举一下就会发现，某些不同的放置顺序，最终得到的铺设图案可能是一样的。DFS会把这些顺序都当作不同的搜索路径，导致重复计数。更致命的是，随着棋盘变大，搜索树的分支会呈指数级增长。对于N=10, M=10的棋盘，格子数100，即使有各种剪枝，搜索空间也依然是天文数字，不可能在规定时间内（通常1秒）完成计算。
那么，如何避免重复和爆炸？我们需要换一个视角。不要从“当前该放哪块砖”的角度思考，而是从“当前行的覆盖情况”来思考。这就是按行递推的思想。我们一行一行地铺。当铺到第i行时，第i-1行及其以上的所有行必须已经被完全铺满（因为砖不会悬空）。此时，第i行某些格子可能已经被从上一行竖着放下来的砖覆盖了，剩下的格子需要我们在本行内，通过横放砖块或者和下一行配合竖放砖块来覆盖。
如何描述一行的“覆盖情况”？我们用状态压缩。用一个M位的二进制数来表示一行中每个格子的状态。通常，我们用1表示这个格子已经被覆盖（可能是被上一行竖下来的砖盖住了，也可能是被本行横放的砖盖住了），用0表示这个格子还空着，需要被覆盖。注意，这个“需要被覆盖”是相对于当前决策阶段而言的。当我们决策第i行时，1表示这个位置不能再放砖的起点（因为已经被占了），0表示这个位置必须被作为某块砖的起点来覆盖（要么横放，要么和下一行一起竖放）。
有了这个定义，我们就可以设计DP状态了。设dp[i][state]表示铺完前i行，并且第i行的覆盖状态为state时，所有可能的方案总数。这里state就是那个M位的二进制整数，它的二进制表示对应第i行每个格子的“是否已被覆盖”状态。
关键转移：如何从dp[i-1][prev_state]转移到dp[i][curr_state]？这意味着，已知第i-1行铺完后的状态是prev_state，我们如何摆放砖块，使得第i-1行被完全铺满（即所有prev_state中的0都必须被填上），并且同时决定了第i行的状态curr_state。
这个过程可以通过一个DFS函数来枚举。这个DFS不是在全盘搜索，而是在两行之间，针对特定的prev_state，枚举所有可能的砖块摆放方式，并计算出每种摆放方式产生的curr_state。具体来说：
- 我们从第
i-1行的最左边格子开始扫描（用列索引j从0到M-1）。 - 如果
prev_state在第j位是1（该位置已被覆盖），那么我们什么都不能做，直接跳到下一列j+1。 - 如果
prev_state在第j位是0（该位置空着，必须被覆盖），那么我们有两种选择：- 横放：如果
j+1 < M且prev_state在第j+1位也是0，我们可以放一块横砖，覆盖(i-1, j)和(i-1, j+1)。这次放置没有影响到第i行的状态，所以curr_state对应位不变。然后我们继续从j+2开始处理。 - 竖放：我们放一块竖砖，覆盖
(i-1, j)和(i, j)。这意味着第i-1行的j位置被覆盖了，同时第i行的j位置也被覆盖了。所以，我们需要在curr_state的第j位标记为1。然后我们继续从j+1开始处理。
- 横放：如果
- 当我们扫描完所有列后，必须确保
prev_state中所有的0都被覆盖了（即我们成功找到了一种铺法）。此时产生的curr_state就是一个有效的、从prev_state转移而来的新状态。那么就有dp[i][curr_state] += dp[i-1][prev_state]。
这个枚举两行之间铺法的DFS，是解决整个问题的核心引擎。它保证了我们既能考虑到所有可能的砖块摆放，又避免了全盘搜索的冗余。最终，我们想要求的是铺满前N行的方案数。我们可以想象存在第N+1行，并且要求第N行必须被完全铺满（不能有砖头伸到第N+1行）。这对应着最终状态dp[N][(1<<M)-1]，即第N行的状态是所有位都是1（表示全部被覆盖，没有空位需要伸到下一行）。
3. 核心算法实现：DFS枚举与DP转移的代码级详解
理论说清楚了，我们来看代码如何实现。这里会给出Java版本的核心代码，并逐行解释其意图和细节。我们假设棋盘规模N和M都不太大（比如N, M <= 15），这样状态总数1<<M是可行的（最多2^15 = 32768种状态）。
首先，定义一些全局变量和输入：
int N, M; // 棋盘的行数和列数 long[][] dp; // dp[i][state]，使用long防止溢出dp数组为什么用long？因为方案数可能非常大，即使取模前也可能超出int范围。
接下来是核心的DFS函数，它负责枚举从上一行状态prev出发，所有能铺满上一行并得到当前行状态now的方案。我们采用递归实现，参数col表示当前处理到的列索引，prev和now是当前的状态，dpNext是一个临时数组，用于累积下一行状态的方案数。
/** * DFS枚举铺砖方式 * @param col 当前处理的列索引 (0-based) * @param prev 第i-1行的状态（二进制位1表示已覆盖，0表示待覆盖） * @param now 第i行的当前状态（二进制位1表示被竖砖覆盖） * @param dpNext 用于累加dp[i][now]的数组 */ private static void dfs(int col, int prev, int now, long[] dpNext) { // 基准情况：已经处理完所有列 if (col == M) { // 当处理完所有列时，prev必须全部变为1（即prev==fullMask），表示上一行已完全铺满 // 如果prev==fullMask，说明我们找到了一种合法的铺设方式，它导致了下一行状态为now if (prev == ((1 << M) - 1)) { dpNext[now] += dp[currentRow][prevStartState]; // 注意这里累加的是上一行的某个状态值 // 在实际循环中，prevStartState是固定的，dpNext[now]会累加所有能转移到now的prev状态的方案数 // 这里为了逻辑清晰，先理解dfs的作用是找到一条转移路径。 } return; } // 情况1：prev的当前列已经是1（被覆盖），直接跳过，处理下一列 if ((prev & (1 << col)) != 0) { dfs(col + 1, prev, now, dpNext); return; } // 情况2：prev的当前列是0，必须覆盖它。有两种覆盖方式。 // 方式A：尝试横放砖块 (覆盖 prev行的 col 和 col+1) if (col + 1 < M && (prev & (1 << (col + 1))) == 0) { // 横放只影响prev行，将prev的col和col+1位都标记为1 int newPrev = prev | (1 << col) | (1 << (col + 1)); dfs(col + 2, newPrev, now, dpNext); // 跳过两列 } // 方式B：尝试竖放砖块 (覆盖 prev行的col 和 now行的col) // 竖放会影响两行：将prev的col位标记为1，同时将now的col位也标记为1 int newNow = now | (1 << col); int newPrev = prev | (1 << col); dfs(col + 1, newPrev, newNow, dpNext); }重要提示：上面的dfs函数是一个简化的逻辑展示，它隐含了一个重要的点：dp[currentRow][prevStartState]的值需要在调用前被知晓。在实际的主DP循环中，我们是对每个prevStartState分别调用这个DFS，来更新下一行的所有可能状态。
因此，更常见的写法是将DFS封装成一个“预处理”步骤，或者直接在DP循环内部调用。下面我们来看主DP循环的经典写法，它直接体现了“枚举上一行状态，通过DFS更新下一行状态”的过程：
// 初始化DP数组，行数为N+1（多一行方便处理），状态数为 1<<M dp = new long[N + 1][1 << M]; // 第0行的状态是全1（想象第0行之上已经铺满，没有任何空位需要伸到第1行） dp[0][(1 << M) - 1] = 1; // 遍历每一行 for (int i = 0; i < N; i++) { // 遍历第i行的所有可能状态 for (int state = 0; state < (1 << M); state++) { if (dp[i][state] == 0) continue; // 如果该状态不可达，跳过 // 对于第i行的每个可达状态state，枚举所有铺法，得到第i+1行的各种状态nextState // 这里用一个辅助数组nextDP来暂存第i+1行的结果 long[] nextDP = new long[1 << M]; // 调用DFS，从第0列开始，初始时第i行状态为state（需要被铺满），第i+1行状态为0（空） dfs(0, state, 0, nextDP); // 将DFS枚举得到的所有转移方案，累加到dp[i+1][nextState]中 for (int nextState = 0; nextState < (1 << M); nextState++) { if (nextDP[nextState] != 0) { dp[i + 1][nextState] = (dp[i + 1][nextState] + dp[i][state] * nextDP[nextState]) % MOD; } } } } // 最终答案：铺完前N行，且第N行状态为全1（没有空位） long answer = dp[N][(1 << M) - 1];这里有几个极其关键的细节和易错点：
初始化
dp[0][fullMask] = 1：这是状态的起点。它表示第0行（一个虚拟的、已经铺好的行）的状态是全满的，只有这样，我们才能开始铺第1行。这是一个边界条件的设定，需要理解其物理意义。DFS中的
prev和now：在dfs(col, prev, now, nextDP)调用时，prev参数是“当前需要被铺满的行”的状态，它最初是state（第i行状态）。在DFS递归过程中，我们通过放置砖块来修改prev，目标是将其所有位变成1。now参数是“下一行”的状态，初始为0，在放置竖砖时，我们会将now的对应位设为1。当DFS递归到底（col == M）且prev变为全1时，我们就得到了一种合法的铺法，其对应的下一行状态就是最终的now。nextDP数组的作用：对于固定的一个state，DFS会枚举出所有能铺满它并产生的nextState。nextDP[nextState]记录的是从这一个特定的state出发，能转移到nextState的方案数。这个数通常是1（因为对于固定的state，每种铺法唯一确定一个nextState），但在某些更复杂的砖块形状下可能大于1。所以最终转移方程是dp[i+1][nextState] += dp[i][state] * nextDP[nextState]。取模操作：答案很大，必须在每次加法后取模。注意
dp[i][state]和nextDP[nextState]相乘也可能溢出，需要使用long类型并在计算后取模。时间复杂度：外层循环
N次，内层循环状态数S = 1<<M，对于每个状态都要进行一次DFS枚举。DFS枚举的时间复杂度与M相关，最坏是O(2^M)？其实不是，因为DFS的递归树分支是常数（横放或竖放），其深度是M，所以一次DFS是O(2^M)吗？实际上，由于我们通过prev的状态来剪枝（遇到1就跳过），枚举所有铺法的复杂度大约在O(2^{M/2})量级，是一个卡特兰数相关的复杂度。总体复杂度约为O(N * S * F(M))，其中F(M)是枚举铺法的复杂度。当M<=15时，这个算法是可行的。
4. 性能优化与边界处理：让代码真正高效可靠
基础的状压DP实现后，我们还需要考虑一些优化和边界情况，以确保代码在竞赛环境中既快又稳。
4.1 预处理转移关系
在上述循环中，我们对每一行的每个状态state都调用了一次DFS来枚举转移。但仔细想想，转移关系(state -> nextState)只与M有关，与行号i无关！这意味着我们可以提前把所有可能的转移关系预处理出来，存到一个列表或数组中。这样在DP主循环中，就可以直接查表，省去了大量重复的DFS调用。
预处理可以这样实现：
// trans[state] 是一个列表，存放所有能从state转移到的(nextState, ways)对 List<int[]>[] trans = new List[1 << M]; // ways通常为1，可以只存nextState for (int s = 0; s < (1 << M); s++) { trans[s] = new ArrayList<>(); long[] tmp = new long[1 << M]; dfs(0, s, 0, tmp); // 使用一个临时数组接收DFS结果 for (int ns = 0; ns < (1 << M); ns++) { if (tmp[ns] != 0) { trans[s].add(new int[]{ns, (int)tmp[ns]}); // 存储转移到的状态和方案数 } } } // 主DP循环变为 for (int i = 0; i < N; i++) { for (int s = 0; s < (1 << M); s++) { if (dp[i][s] == 0) continue; for (int[] t : trans[s]) { int ns = t[0]; int ways = t[1]; dp[i+1][ns] = (dp[i+1][ns] + dp[i][s] * ways) % MOD; } } }这个优化在M较大时效果显著，属于典型的“空间换时间”。
4.2 处理大数取模与输入限制
蓝桥杯的题目通常要求结果对某个数取模，比如1000000007。我们需要在每次加法、乘法后及时取模。使用long类型存储中间结果可以避免溢出。另外，要留意题目中N和M的范围。如果M > N，我们可以交换N和M，因为覆盖方案数只与棋盘面积和形状有关，与行列方向无关。并且，当M较大时，状态数1<<M会指数增长，可能超出内存或时间限制。有时题目会保证N*M是偶数（因为1x2砖块覆盖，总面积必须是偶数），这也是一个有用的剪枝条件：如果N*M是奇数，答案直接为0。
4.3 滚动数组优化空间
我们的DP数组是dp[N+1][1<<M]。如果N很大（比如几百），而1<<M也很大（比如M=12，状态数4096），这个二维数组可能占用几百MB内存，导致内存超限。观察转移方程dp[i+1][next]只依赖于dp[i][prev]。因此，我们可以使用滚动数组，只保留两行状态。
long[][] dp = new long[2][1 << M]; int cur = 0, nxt = 1; dp[cur][(1<<M)-1] = 1; for (int i = 0; i < N; i++) { Arrays.fill(dp[nxt], 0); // 清空下一行 for (int s = 0; s < (1 << M); s++) { if (dp[cur][s] == 0) continue; for (int[] t : trans[s]) { int ns = t[0]; int ways = t[1]; dp[nxt][ns] = (dp[nxt][ns] + dp[cur][s] * ways) % MOD; } } // 交换当前行和下一行 int tmp = cur; cur = nxt; nxt = tmp; } long answer = dp[cur][(1 << M) - 1]; // 注意最后一行结束后，cur指向的是第N行的状态这个优化将空间复杂度从O(N * S)降到了O(S)，是处理大规模N时的必备技巧。
4.4 针对特定砖块形状的DFS修改
我们以上讨论的都是1x2的砖块。如果砖块形状变化，比如2x2的方块，或者L形的三格砖（俄罗斯方块里的那种），核心的状压DP框架不变，唯一需要修改的就是那个枚举铺法的DFS函数。你需要根据新砖块的形状，设计新的放置规则。
例如，对于2x2方块，它一次覆盖两行两列。那么在DFS枚举时，当遇到prev行的一个0，你可以选择放置一个2x2方块，前提是prev行的j, j+1位都是0，并且now（代表下一行）的j, j+1位当前也都是0（因为方块会覆盖到下一行）。放置后，prev和now的对应四位都要标记为1。
对于L形砖，情况更复杂，可能有多种旋转形态。你需要枚举所有可能的放置方式，并确保放置后不超出边界、不重叠。这会使DFS的代码变得更复杂，但原理相通：都是通过递归，从左到右扫描，尝试用各种砖块填充prev行中的0，并更新now行的状态。
5. 实战演练与调试技巧：从理论到AC的最后一公里
理解了算法，写出了代码，不代表就能AC。在竞赛中，调试和验证是关键一步。以下是一些实战心得：
1. 从小规模数据开始验证不要一上来就用N=10, M=10测试。先测试N=1, M=2（答案应为1，横放一块砖），N=2, M=2（答案应为2，要么都横放，要么都竖放）。再测试N=2, M=3，可以手工计算或搜索网上已知的经典结果（多米诺覆盖 2x3 棋盘有3种方案）。用这些简单案例验证你的DP和DFS逻辑是否正确。
2. 打印中间状态进行调试如果结果不对，可以打印出预处理后的转移关系trans。看看对于某个简单的state（比如0b000），它能转移到哪些nextState，转移方案数是否正确。也可以打印出每一行DP结束后的dp[i]数组，观察状态值的分布是否合理。
3. 注意整型溢出和取模这是最隐蔽的bug来源。确保所有dp值都用long，并且在dp[i][s] * ways这里，即使dp[i][s]和ways都是int，它们的乘积也可能超出int范围，所以必须先转换成long再计算和取模。Java中两个int相乘，结果还是int，可能会溢出后才赋值给long变量。安全的写法是：(dp[i][s] * (long)ways) % MOD。
4. 处理N=0或M=0的边界虽然题目通常不会给出这种数据，但好的习惯是加上判断。当N==0 || M==0时，一个空棋盘，铺满的方案数应该是1（什么都不铺）。但根据我们的DP初始化dp[0][fullMask]=1，如果M=0，那么fullMask = (1<<0)-1 = 0，最终答案dp[N][0]也是1，逻辑自洽。但为了安全，可以特殊处理。
5. 利用对称性剪枝（高级优化）对于某些对称的棋盘，很多状态是等价的。例如，状态0b0011和0b1100在覆盖方案数上可能是对称的。我们可以定义一个状态的最小表示（比如循环左移/右移后取最小值），将等价状态归并，进一步减少状态数。但这属于竞赛中的高级技巧，在时间紧迫的情况下，优先保证基础算法的正确性更为重要。
最后，将完整的、经过优化的代码整合起来，并处理好输入输出，你就能稳稳地拿下这类“铺瓷砖”问题。记住，其核心永远是：状态压缩表示行覆盖情况，DFS枚举两行间的所有合法填充方式，利用DP按行递推累计方案数。把这个模型吃透，它就从一个令人头疼的难题，变成了你算法工具箱里一件趁手的兵器。
)
