UVa 12117 ACM Puzzles

题目描述ACM\texttt{ACM}ACM儿童机器协会计划为儿童设计一种新型拼图。所有拼图的尺寸都是3×N3 \times N3×N并使用222222种特定的拼图块某些块可以重复使用。为了防止假冒产品ACM\texttt{ACM}ACM生产的拼图在出售时只会保留某些特定的解法。给定NNN0N20010 N 20010N2001计算使用给定拼图块可以组成多少种不同的解法。不允许旋转拼图块但每种块可以使用任意多次。有些块只是其他块的旋转版本但也不能通过旋转使其变成另一种块。输入格式输入文件包含多行每行一个整数NNN0N20010 N 20010N2001。输入以一行单独的000结束。输出格式对于每个NNN输出一行格式为Case k: ans其中answerSmod 1012answer S \mod 10^{12}answerSmod1012SSS是3×N3 \times N3×N拼图的解法总数。样例输入5 100 0样例输出Case 1: 26 Case 2: 584039302899题目分析问题本质这是一个铺砖问题Tiling Problem\texttt{Tiling Problem}Tiling Problem的变种用222222种给定的、不可旋转的拼图块填满3×N3 \times N3×N的矩形区域。由于NNN最大可达200020002000需要设计一个高效的动态规划算法。关键难点块形状复杂222222种块形状各异宽度可能是111、222或333列。不允许旋转即使某些块看起来是旋转对称的也被视为不同的块。大数取模结果需要对101210^{12}1012取模说明结果可能非常大。解题思路分析1. 状态定义观察到拼图块的宽度最多为333列我们可以采用列轮廓线动态规划的思路。定义状态为dp[i][p][q][r]dp[i][p][q][r]dp[i][p][q][r]表示已经填充到第iii列第i1i1i1列的三行分别有ppp、qqq、rrr个格子已被占用从之前的块延伸过来的部分其中p,q,r∈{0,1,2}p, q, r \in \{0, 1, 2\}p,q,r∈{0,1,2}表示第i1i1i1列有多少个格子已被占据这个状态表示当前填充的前沿位置以及下一列的“欠债”情况即有多少格子已经被之前的块占用。2. 状态转移对于每个状态(i,p,q,r)(i, p, q, r)(i,p,q,r)我们尝试放置222222种拼图块中的一种。每个拼图块被定义为一个3×33 \times 33×3的字符数组其中*表示该位置被块占用 空格表示该位置为空转移时需要检查块的左侧三列是否与当前偏移(p,q,r)(p, q, r)(p,q,r)匹配即对应位置必须是*块的左侧不能有额外的填充超出边界计算放置块后新的偏移量3. 偏移归一化放置一个块后可能会产生新的偏移。为了保持状态空间的大小可控我们进行偏移归一化计算新的p′,q′,r′p, q, rp′,q′,r′值后将它们减去最小值使至少一个值为000其他值在000到222之间。这样状态数量被限制在合理的范围内。4. 算法流程初始化dp[0][0][0][0]1dp[0][0][0][0] 1dp[0][0][0][0]1空棋盘一种方案对于每个iii从000到200020002000遍历所有(p,q,r)(p, q, r)(p,q,r)状态对于每个状态尝试放置222222种块中的每一种检查放置是否合法计算新状态并更新dpdpdp值对于输入的NNN答案就是dp[N][0][0][0]dp[N][0][0][0]dp[N][0][0][0]完全填满NNN列且无偏移5. 复杂度分析时间复杂度O(N×33×22)≈O(600N)O(N \times 3^3 \times 22) \approx O(600N)O(N×33×22)≈O(600N)对于N≤2000N \leq 2000N≤2000可以接受空间复杂度O(N×33)≈O(27N)O(N \times 3^3) \approx O(27N)O(N×33)≈O(27N)可以通过滚动数组优化但本题NNN较小直接开数组即可为什么这种方法有效状态压缩通过偏移量表示未完成的部分避免了记录整个棋盘状态完全性枚举所有块和所有可能的位置不会遗漏任何合法解高效性状态数有限转移代价小适合NNN较大的情况参考代码// ACM Puzzles// UVa ID: 12117// Verdict: Accepted// Submission Date: 2026-01-30// UVa Run Time: 0.000s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;typedeflonglongll;constll MOD1000000000000LL;// 22种拼图块的定义charpuzzleBlocks[22][3][4]{{* ,* ,* },{* ,** ,* },{** , * ,** },{ * ,** ,** },{ * ,***, * },{** ,* ,** },{ * ,** , * },{ *, **,** },{** , **, *},{ * ,** ,* },{* ,** , * },{** ,** ,* },{** ,** , * },{** ,* ,* },{** , * , * },{ **,** ,* },{* ,** , **},{* ,* ,** },{ * , * ,** },{***, * , * },{ * , * ,***},{* ,** ,** }};ll dp[2005][3][3][3];// dp[i][p][q][r]voidinitialize(){// 初始化dp数组为0memset(dp,0,sizeof(dp));dp[0][0][0][0]1;// 起始状态for(inti0;i2000;i){for(intp0;p3;p)for(intq0;q3;q)for(intr0;r3;r){ll currentValdp[i][p][q][r];if(currentVal0)continue;// 尝试放置22种块中的每一种for(intblockIdx0;blockIdx22;blockIdx){// 检查块左侧三列是否与当前偏移匹配if(puzzleBlocks[blockIdx][0][p]!*||puzzleBlocks[blockIdx][1][q]!*||puzzleBlocks[blockIdx][2][r]!*)continue;// 检查左侧是否有额外填充不能超出边界if(p0puzzleBlocks[blockIdx][0][p-1]! )continue;if(q0puzzleBlocks[blockIdx][1][q-1]! )continue;if(r0puzzleBlocks[blockIdx][2][r-1]! )continue;// 计算放置后的新偏移intnewPip,newQiq,newRir;for(intk0;k3;k){if(puzzleBlocks[blockIdx][0][k]*)newP;if(puzzleBlocks[blockIdx][1][k]*)newQ;if(puzzleBlocks[blockIdx][2][k]*)newR;}// 标准化偏移减去最小值intminValmin({newP,newQ,newR});intoffsetPnewP-minVal;intoffsetQnewQ-minVal;intoffsetRnewR-minVal;// 更新dp值dp[minVal][offsetP][offsetQ][offsetR]currentVal;if(dp[minVal][offsetP][offsetQ][offsetR]MOD)dp[minVal][offsetP][offsetQ][offsetR]%MOD;}}}}intmain(){initialize();intn,caseNo1;while(cinnn!0)coutCase caseNo: dp[n][0][0][0]\n;return0;}总结本题是一个经典的状态压缩动态规划问题通过巧妙的状态设计将复杂的铺砖问题转化为可管理的动态规划。关键点在于偏移量状态表示用p,q,rp, q, rp,q,r表示下一列的占用情况偏移归一化通过减去最小值控制状态空间大小完全枚举尝试所有222222种块的放置方式这种解法具有通用性可以应用于类似的拼图或铺砖问题。理解这种状态表示和转移方法对于解决复杂的组合计数问题非常有帮助。