一，拼接覆盖问题
给出若干个积木块部件，要求放到指定区域内，使得没有重叠。
二，冗余面积处理
如果积木块的总面积，小于指定区域的总面积，那么可以新增若干个虚拟的最小单元，拼好之后再把这些最小单元去掉。
这样，带冗余面积的拼接覆盖问题，就转化成了常见的精确面积的覆盖问题。
三，部件和部件之间的区分问题
如果有2个重复的块，直接当他们是2个不重复的块，一般都没有问题。
四，单个部件的朝向问题
一般有3种场景：（1）只能平移（2）可以平移、旋转（3）可以平移、旋转、翻转
实际上，只要能翻转自然就能实现旋转。
拼接覆盖问题也可以转成精确覆盖问题。
二维非重复块拼接覆盖
只要枚举所有的块，每个块的每一种可能性就是dancing links的一行，待覆盖区域的每个格子就是一列。除此之外，还要限制每个块只能被用1次，这也是对应一列。
PS：如果有2个重复的块，直接当他们是2个不重复的块，也没有问题。
struct Grid { int r, c; Grid(int rr, int cc) :r(rr), c(cc) {} bool operator<(const Grid& g) const { if (r == g.r)return c < g.c; return r < g.r; } }; struct Block //一个块的所有形态 { vector<vector<Grid>>grids; Block(vector<vector<Grid>>g, int maxDr, int maxDc, const map<Grid, int>& m)//块的所有形态在最小位置包含的格子,最大偏移,待覆盖区域包含的格子 { this->m = m; for (auto& g2 : g) { for (int i = 0; i < maxDr; i++)for (int j = 0; j < maxDc; j++) { for (auto& x : g2)x.r += i, x.c += j; if (inBoard(g2))grids.push_back(g2); for (auto& x : g2)x.r -= i, x.c -= j; } } } Block() {} private: map<Grid, int>m; bool inBoard(vector<Grid>& g) { for (auto& x : g)if (!m[x])return false; return true; } }; vector<vector<Grid>> Cover(vector<Block>blocks, map<Grid, int>& mg)//所有块，待覆盖区域包含的格子编号为1,2,3... { int m = 0, maxNum = 0; for (auto& block : blocks) { m += block.grids.size(); maxNum += block.grids.size() * (block.grids[0].size()+1); } DancingLink d(m, mg.size() + blocks.size(), maxNum); int r = 0; map<int, int>mrow; for (int i = 0; i < blocks.size(); i++) { mrow[r + 1] = i + 1; for (auto& grids : blocks[i].grids) { ++r; for (auto& g : grids)d.push(r, mg[g]); d.push(r, i + 1 + mg.size()); } } d.dfs(); vector<int> rows = d.rows; vector<vector<Grid>> ans; for (auto row : rows) { int id = 0; while (!mrow[row])row--, id++;; ans.push_back(blocks[mrow[row] - 1].grids[id]); } return ans; }应用示例：
日历拼图
三维重复块拼接覆盖
假如部分块是没有数量限制的（从0到正无穷都可以），那么只需要取消“这个块只能被用1次”这个限制对应的列即可，其他的不变。
struct Grid { int r, c, h; Grid(int rr, int cc,int hh) :r(rr), c(cc),h(hh) {} bool operator<(const Grid& g) const { if (h == g.h) { if (r == g.r)return c < g.c; return r < g.r; } return h < g.h; } }; struct Block //一个块的所有形态 { vector<vector<Grid>>grids; Block(vector<vector<Grid>>g, int maxDr, int maxDc, int maxDh, const map<Grid, int>& m)//块的所有形态在最小位置包含的格子,最大偏移,待覆盖区域包含的格子 { this->m = m; for (auto& g2 : g) { for (int i = 0; i < maxDr; i++)for (int j = 0; j < maxDc; j++)for(int k=0;k<maxDh;k++) { for (auto& x : g2)x.r += i, x.c += j, x.h += k; if (inBoard(g2))grids.push_back(g2); for (auto& x : g2)x.r -= i, x.c -= j, x.h -= k;; } } } Block() {} private: map<Grid, int>m; bool inBoard(vector<Grid>& g) { for (auto& x : g)if (!m[x])return false; return true; } }; vector<vector<Grid>> Cover(vector<Block>blocks, map<int,int>ids, map<Grid, int>& mg)//所有块，不限数量的块的id, 待覆盖区域包含的格子编号为1,2,3... { int m = 0, maxNum = 0; for (auto& block : blocks) { m += block.grids.size(); maxNum += block.grids.size() * (block.grids[0].size() + 1); } DancingLink d(m, mg.size() + blocks.size() - ids.size(), maxNum); int r = 0, c = mg.size(); map<int, int>mrow; for (int i = 0; i < blocks.size(); i++) { mrow[r + 1] = i + 1; for (auto& grids : blocks[i].grids) { ++r; for (auto& g : grids)d.push(r, mg[g]); if(ids[i]==0)d.push(r, ++c); } } d.dfs(); vector<int> rows = d.rows; vector<vector<Grid>> ans; for (auto row : rows) { int id = 0; while (!mrow[row])row--, id++;; ans.push_back(blocks[mrow[row] - 1].grids[id]); } return ans; }应用示例：
三维T型拼图
int r,c,h,blockNum; //自定义行列数,块数 map<Grid, int> ng,mg; //ng是自定义挖掉的格子，mg是有效格子 vector<Block>blocks;//自定义每个块的所有形态在最小位置包含的格子 map<int, int>ids; vector<Grid> rotate(vector<Grid>& g) { int maxRow = 0, t; for (auto& gi : g)maxRow = max(maxRow, gi.r); for (auto& gi : g)t = gi.c, gi.c = maxRow - gi.r, gi.r = t; return g; } vector<Grid> rotate2(vector<Grid> g) { int maxH = 0, t; for (auto& gi : g)maxH = max(maxH, gi.h); for (auto& gi : g)t = gi.c, gi.c = maxH - gi.h, gi.h = t; return g; } void init1() { r = 6, c = 6, h=6, blockNum = 1; ng.clear(), mg.clear(); } void init2() { vector<Grid>v1 = { {0,0,0},{0,1,0},{0,2,0},{1,1,0} }; vector<Grid>v2 = { {0,0,0},{0,1,0},{0,2,0},{0,1,1} }, v3 = rotate2(v2), v4 = rotate2(v3), v5 = rotate2(v4); blocks[0] = Block{ { v1,rotate(v1),rotate(v1),rotate(v1),v2,rotate(v2),v3,rotate(v3),v4,rotate(v4),v5,rotate(v5)}, r, c,h, mg }; ids[0] = 1; } void solve() { init1(); int id = 0; for (int i = 0; i < r; i++)for (int j = 0; j < c; j++) for (int k = 0; k < h; k++) { if (ng[Grid{ i, j ,k }] == 0)mg[Grid{ i, j,k }] = ++id; } blocks.resize(blockNum); init2(); vector<vector<Grid>> grids = Cover(blocks,ids, mg); vector<vector<vector<int>>>v(r); for (int i = 0; i < r; i++) { v[i].resize(c); for (int j = 0; j < c; j++)v[i][j].resize(h); } for (int i = 0; i < grids.size(); i++) { for (auto& g : grids[i])v[g.r][g.c][g.h] = i + 1; } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { for (int k = 0; k < h; k++)cout << v[i][j][k] << " "; cout << endl; } cout << endl; } } int main() { ios::sync_with_stdio(false); clock_t start, endd; start = clock(); freopen("D:ans.txt", "w", stdout); solve(); endd = clock(); double endtime = (double)(endd - start) / CLOCKS_PER_SEC; cout << "Total time:" << endtime << endl; //s为单位 return 0; }输出：
1 1 1 2 2 2
7 7 7 10 10 10
20 20 20 23 23 23
21 21 21 31 31 31
24 21 37 36 31 32
3 3 3 4 4 4
5 1 8 9 2 11
13 7 9 9 10 27
25 20 35 9 23 27
28 35 35 35 49 27
24 37 37 36 32 32
24 3 39 36 4 33
5 5 8 8 11 11
13 13 34 42 42 42
25 25 34 34 42 27
28 28 34 49 49 49
24 30 37 36 48 32
26 39 39 41 33 33
5 14 8 43 44 11
13 29 43 43 43 54
25 29 29 50 54 54
28 29 50 50 50 54
30 30 40 48 48 48
26 26 39 41 41 33
14 14 14 44 44 44
16 16 16 51 51 51
18 16 17 52 51 53
18 18 40 52 52 47
18 30 40 52 47 47
26 19 40 41 38 47
6 6 6 12 12 12
15 6 17 45 12 53
15 15 17 45 45 53
15 22 17 45 46 53
22 22 22 46 46 46
19 19 19 38 38 38
Total time:0.953
