题目描述给定一个宽为www、高为hhh的矩形表面以及若干组矩形瓷砖。同一组内的瓷砖尺寸完全相同不同组的尺寸可能不同。每种瓷砖有给定的数量。允许将瓷砖旋转90∘90^\circ90∘。所有瓷砖必须全部使用且不能重叠拼成完整的w×hw \times hw×h矩形。两个拼法被视为不同当且仅当至少存在一个瓷砖组其所有瓷砖在两次拼法中的放置位置和方向模式不同同一组内的瓷砖不区分个体。输入保证至少存在一种拼法。对于每组数据输出不同拼法的总数。输入格式每组数据格式为w h n m1 w1 h1 m2 w2 h2 ... mn wn hn其中www、hhh为矩形的宽和高满足0w,h≤1000 w, h \le 1000w,h≤100nnn为相似组的数量满足0n≤100 n \le 100n≤10第kkk组有mkm_kmk块瓷砖其宽为wkw_kwk、高为hkh_khk所有尺寸均为整数。输入包含多组数据直到文件结束。输出格式对于每组数据输出一行表示该拼图的不同拼法总数。样例输入3 2 2 2 1 1 2 1 2 5 2 2 2 1 1 4 1 2输出11 56题目分析本问题是一个二维矩形平铺计数问题。矩形面积最大为100×10010000100 \times 100 10000100×10010000瓷砖总数可能较多但n≤10n \le 10n≤10不同尺寸的种类有限。直接枚举所有瓷砖的放置位置和顺序会导致指数爆炸必须设计高效的搜索策略。关键性质若我们按行优先顺序扫描矩形找到第一个未被覆盖的格子则任何能够覆盖这个格子的有效铺法中覆盖该格子的瓷砖的左上角必然恰好位于该格子。这是因为如果一块瓷砖覆盖了该格子其左上角不可能在该格子的上方或左侧否则那个更靠前的格子会被覆盖与“第一个空白格”矛盾。因此在搜索过程中每次只需固定待放置瓷砖的左上角为当前第一个空白格然后枚举所有剩余组及其旋转方向判断能否在该位置放下瓷砖并继续递归。这种方法不会产生重复因为每个合法铺法在搜索树中对应唯一一条路径由于空白格的选取顺序完全由铺法本身决定。瓷砖可以旋转90∘90^\circ90∘因此对于每一种瓷砖我们只需考虑两种方向原始方向和旋转90∘90^\circ90∘后的方向如果宽高相等则旋转后相同此时只保留一个方向。解题思路搜索框架采用深度优先搜索DFS\texttt{DFS}DFS进行回溯。具体步骤如下维护一个二维布尔数组used[h][w]\textit{used}[h][w]used[h][w]标记每个格子是否已被覆盖。每次进入DFS\texttt{DFS}DFS时扫描整个矩形找到第一个usedfalse\textit{used} \texttt{false}usedfalse的格子(x,y)(x, y)(x,y)。若不存在这样的格子说明矩形已完全铺满计数器加111并返回。若存在空白格(x,y)(x, y)(x,y)则遍历所有瓷砖组。对于每个剩余数量大于000的组尝试该组的每个方向宽w′ww′高h′hh′。检查以(x,y)(x, y)(x,y)为左上角大小w′×h′w \times hw′×h′的矩形是否完全在矩形内部且所有格子均为空白。若满足则放置该瓷砖标记相应格子为已占用递归调用自身返回后回溯恢复格子状态和瓷砖数量。优化措施按面积排序将瓷砖组按面积wk×hkw_k \times h_kwk×hk从大到小排序优先尝试大面积瓷砖可有效减少搜索分支加快剪枝。可行性剪枝在搜索过程中当前剩余的空白面积必须等于所有剩余瓷砖面积之和这是输入保证的因此无需额外检查。算法复杂度搜索的最坏情况仍然可能很大但本题数据规模w,h≤100w, h \le 100w,h≤100n≤10n \le 10n≤10在合理剪枝下可通过。实际测试表明该回溯方法能够高效运行。代码实现// Tile Puzzle// UVa ID: 798// Verdict: Accepted// Submission Date: 2026-07-04// UVa Run Time: 0.930s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structGroup{intm;// 剩余数量intw,h;// 原始宽高intdirCnt;// 有效方向数1 或 2intdirs[2][2];// 每个方向的宽、高};intW,H,N;vectorGroupgroups;boolused[100][100];unsignedlonglongans;voiddfs(){// 找第一个空白格intx-1,y-1;for(inti0;iHx-1;i)for(intj0;jW;j)if(!used[i][j]){xj;yi;break;}if(x-1){ans;return;}for(size_t idx0;idxgroups.size();idx){Groupggroups[idx];if(g.m0)continue;for(intd0;dg.dirCnt;d){intwwg.dirs[d][0],hhg.dirs[d][1];if(xwwW||yhhH)continue;booloktrue;for(intry;ryhhok;r)for(intcx;cxwwok;c)if(used[r][c])okfalse;if(!ok)continue;// 放置for(intry;ryhh;r)for(intcx;cxww;c)used[r][c]true;--g.m;dfs();// 回溯g.m;for(intry;ryhh;r)for(intcx;cxww;c)used[r][c]false;}}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);while(cinWHN){groups.clear();for(inti0;iN;i){intm,w,h;cinmwh;Group g;g.mm;g.ww;g.hh;g.dirCnt0;// 原始方向g.dirs[g.dirCnt][0]w;g.dirs[g.dirCnt][1]h;g.dirCnt;// 若宽高不等增加旋转方向if(w!h){g.dirs[g.dirCnt][0]h;g.dirs[g.dirCnt][1]w;g.dirCnt;}groups.push_back(g);}// 按面积从大到小排序加速搜索sort(groups.begin(),groups.end(),[](constGroupa,constGroupb){returna.w*a.hb.w*b.h;});// 清空棋盘for(inti0;iH;i)for(intj0;jW;j)used[i][j]false;ans0;dfs();coutans\n;}return0;}总结本题的核心技巧是利用“第一个空白格”的确定性来唯一化摆放顺序从而避免重复计数。回溯搜索配合按面积排序的剪枝能够有效应对题目给定的规模。关键点包括旋转方向的去重处理宽高相等时只保留一种方向。利用行优先扫描固定放置位置使得每种铺法在搜索树中对应唯一路径。合适的排序策略可显著提升搜索效率。该解法充分利用了问题的几何特性是一种经典且实用的平铺计数方法。 
长河君 · 2026/10/27 18:36:13 · 阅读 1.2k UVa 798 Tile Puzzle
题目描述给定一个宽为www、高为hhh的矩形表面以及若干组矩形瓷砖。同一组内的瓷砖尺寸完全相同不同组的尺寸可能不同。每种瓷砖有给定的数量。允许将瓷砖旋转90∘90^\circ90∘。所有瓷砖必须全部使用且不能重叠拼成完整的w×hw \times hw×h矩形。两个拼法被视为不同当且仅当至少存在一个瓷砖组其所有瓷砖在两次拼法中的放置位置和方向模式不同同一组内的瓷砖不区分个体。输入保证至少存在一种拼法。对于每组数据输出不同拼法的总数。输入格式每组数据格式为w h n m1 w1 h1 m2 w2 h2 ... mn wn hn其中www、hhh为矩形的宽和高满足0w,h≤1000 w, h \le 1000w,h≤100nnn为相似组的数量满足0n≤100 n \le 100n≤10第kkk组有mkm_kmk块瓷砖其宽为wkw_kwk、高为hkh_khk所有尺寸均为整数。输入包含多组数据直到文件结束。输出格式对于每组数据输出一行表示该拼图的不同拼法总数。样例输入3 2 2 2 1 1 2 1 2 5 2 2 2 1 1 4 1 2输出11 56题目分析本问题是一个二维矩形平铺计数问题。矩形面积最大为100×10010000100 \times 100 10000100×10010000瓷砖总数可能较多但n≤10n \le 10n≤10不同尺寸的种类有限。直接枚举所有瓷砖的放置位置和顺序会导致指数爆炸必须设计高效的搜索策略。关键性质若我们按行优先顺序扫描矩形找到第一个未被覆盖的格子则任何能够覆盖这个格子的有效铺法中覆盖该格子的瓷砖的左上角必然恰好位于该格子。这是因为如果一块瓷砖覆盖了该格子其左上角不可能在该格子的上方或左侧否则那个更靠前的格子会被覆盖与“第一个空白格”矛盾。因此在搜索过程中每次只需固定待放置瓷砖的左上角为当前第一个空白格然后枚举所有剩余组及其旋转方向判断能否在该位置放下瓷砖并继续递归。这种方法不会产生重复因为每个合法铺法在搜索树中对应唯一一条路径由于空白格的选取顺序完全由铺法本身决定。瓷砖可以旋转90∘90^\circ90∘因此对于每一种瓷砖我们只需考虑两种方向原始方向和旋转90∘90^\circ90∘后的方向如果宽高相等则旋转后相同此时只保留一个方向。解题思路搜索框架采用深度优先搜索DFS\texttt{DFS}DFS进行回溯。具体步骤如下维护一个二维布尔数组used[h][w]\textit{used}[h][w]used[h][w]标记每个格子是否已被覆盖。每次进入DFS\texttt{DFS}DFS时扫描整个矩形找到第一个usedfalse\textit{used} \texttt{false}usedfalse的格子(x,y)(x, y)(x,y)。若不存在这样的格子说明矩形已完全铺满计数器加111并返回。若存在空白格(x,y)(x, y)(x,y)则遍历所有瓷砖组。对于每个剩余数量大于000的组尝试该组的每个方向宽w′ww′高h′hh′。检查以(x,y)(x, y)(x,y)为左上角大小w′×h′w \times hw′×h′的矩形是否完全在矩形内部且所有格子均为空白。若满足则放置该瓷砖标记相应格子为已占用递归调用自身返回后回溯恢复格子状态和瓷砖数量。优化措施按面积排序将瓷砖组按面积wk×hkw_k \times h_kwk×hk从大到小排序优先尝试大面积瓷砖可有效减少搜索分支加快剪枝。可行性剪枝在搜索过程中当前剩余的空白面积必须等于所有剩余瓷砖面积之和这是输入保证的因此无需额外检查。算法复杂度搜索的最坏情况仍然可能很大但本题数据规模w,h≤100w, h \le 100w,h≤100n≤10n \le 10n≤10在合理剪枝下可通过。实际测试表明该回溯方法能够高效运行。代码实现// Tile Puzzle// UVa ID: 798// Verdict: Accepted// Submission Date: 2026-07-04// UVa Run Time: 0.930s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structGroup{intm;// 剩余数量intw,h;// 原始宽高intdirCnt;// 有效方向数1 或 2intdirs[2][2];// 每个方向的宽、高};intW,H,N;vectorGroupgroups;boolused[100][100];unsignedlonglongans;voiddfs(){// 找第一个空白格intx-1,y-1;for(inti0;iHx-1;i)for(intj0;jW;j)if(!used[i][j]){xj;yi;break;}if(x-1){ans;return;}for(size_t idx0;idxgroups.size();idx){Groupggroups[idx];if(g.m0)continue;for(intd0;dg.dirCnt;d){intwwg.dirs[d][0],hhg.dirs[d][1];if(xwwW||yhhH)continue;booloktrue;for(intry;ryhhok;r)for(intcx;cxwwok;c)if(used[r][c])okfalse;if(!ok)continue;// 放置for(intry;ryhh;r)for(intcx;cxww;c)used[r][c]true;--g.m;dfs();// 回溯g.m;for(intry;ryhh;r)for(intcx;cxww;c)used[r][c]false;}}}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);while(cinWHN){groups.clear();for(inti0;iN;i){intm,w,h;cinmwh;Group g;g.mm;g.ww;g.hh;g.dirCnt0;// 原始方向g.dirs[g.dirCnt][0]w;g.dirs[g.dirCnt][1]h;g.dirCnt;// 若宽高不等增加旋转方向if(w!h){g.dirs[g.dirCnt][0]h;g.dirs[g.dirCnt][1]w;g.dirCnt;}groups.push_back(g);}// 按面积从大到小排序加速搜索sort(groups.begin(),groups.end(),[](constGroupa,constGroupb){returna.w*a.hb.w*b.h;});// 清空棋盘for(inti0;iH;i)for(intj0;jW;j)used[i][j]false;ans0;dfs();coutans\n;}return0;}总结本题的核心技巧是利用“第一个空白格”的确定性来唯一化摆放顺序从而避免重复计数。回溯搜索配合按面积排序的剪枝能够有效应对题目给定的规模。关键点包括旋转方向的去重处理宽高相等时只保留一种方向。利用行优先扫描固定放置位置使得每种铺法在搜索树中对应唯一路径。合适的排序策略可显著提升搜索效率。该解法充分利用了问题的几何特性是一种经典且实用的平铺计数方法。