使用下方的方块铺满上方的三角矩阵，可四个方向旋转：
1 /*
2 10*10
3 **********
4 *********
5 ********
6 *******
7 ******
8 *****
9 ****
10 ***
11 **
12 *
13
14 4144 424 14 444
15 112AAACCDDDD77lvww
16 1222AABCCCDSS7lvvww
17 112BBBBIIIISS7lll w
18 */
19 #include <iostream>
20
21 int tetris[16][4][4][4] = {0};
22 int tetMap[16][16] = {0};
23 int tetIndex = 0;
24
25 void FormatTet(int tetris[4][4])
26 {
27 do
28 {
29 for (int x=0; x<4; ++x)
30 if (tetris[0][x]) goto NE1;
31 for (int y=1; y<4; ++y)for (int x=0; x<4; ++x)
32 tetris[y-1][x] = tetris[y][x];
33 for (int x=0; x<4; ++x)tetris[3][x] = 0;
34 }
35 while (1);
36 NE1:
37 do
38 {
39 for (int y=0; y<4; ++y)
40 if (tetris[y][0]) goto NE2;
41 for (int x=0; x<4; ++x)for (int y=1; y<4; ++y)
42 tetris[y][x-1] = tetris[y][x];
43 for (int y=0; y<4; ++y)tetris[y][3] = 0;
44 }
45 while (1);
46 NE2:;
47 }
48 void Init()
49 {
50 char smap[3][20] = {"112AAACCDDDD77lvww ","1222AABCCCDSS7lvvww","112BBBBIIIISS7lll w"};
51 for (int x=0; x<=18; ++x)
52 {
53 for (int y=0; y<3; ++y)
54 {
55 if (smap[y][x]==' ') continue;
56 char c=smap[y][x];
57 ++tetIndex;
58 for (int y=0; y<3; ++y)
59 for (int dx=0; dx<4; ++dx)
60 {
61 if (smap[y][x+dx]==c) tetris[tetIndex][0][y][dx] = 1, smap[y][x+dx]=' ';
62 }
63 }
64 }
65 for (int n=1; n<=tetIndex; ++n)
66 {
67 FormatTet(tetris[n][0]);
68 for (int ns=1; ns<4; ++ns)
69 {
70 for (int y=0; y<4; ++y)for (int x=0; x<4; ++x)
71 tetris[n][ns][3-x][y] = tetris[n][ns-1][y][x];
72 FormatTet(tetris[n][ns]);
73 }
74 }
75 memset(tetMap, -1, sizeof(tetMap));
76 for (int y=1; y<=10; ++y)for (int x=11-y; x<=10; ++x)
77 tetMap[y][x] = 0;
78 }
79
80 int SetVal(int tetMap[][16], int x, int y, int tetris[4][4], int nVal)
81 {
82 if (nVal)
83 {
84 for (int dy=0; dy<4; ++dy)for (int dx=0; dx<4; ++dx)
85 if (tetris[dy][dx] && tetMap[y+dy][x+dx]) return 0;
86 }
87 for (int dy=0; dy<4; ++dy)for (int dx=0; dx<4; ++dx)
88 if (tetris[dy][dx])tetMap[y+dy][x+dx] = nVal;
89 return 1;
90 }
91
92 int tetUse[16] = {0};
93 int tetMaxSh[16] = {0, 4,1,4,4, 4,2,4,1, 4,4,4,4};
94 int nUse = 0;
95 int DFS()
96 {
97 int nRet = 0;
98 for (int y=1; y<=10; ++y)
99 {
100 for (int x=11-y; x<=10; ++x)
101 {
102 if (tetMap[y][x]) continue;
103 for (int ntet=1; ntet<=tetIndex; ++ntet)
104 {
105 if (tetUse[ntet])continue;
106 for (int ns=0; ns<tetMaxSh[ntet]; ++ns)
107 {
108 int (&tsMap)[4][4] = tetris[ntet][ns];
109 for (int dx=0; dx<4; ++dx)
110 {
111 if (tsMap[0][dx]==0) continue;
112 int bS = SetVal(tetMap, x-dx, y, tsMap, ntet);
113 if (bS)
114 {
115 ++nUse;
116 if (nUse>=tetIndex) return -1;
117 tetUse[ntet] = 1;
118 int nr = DFS();
119 tetUse[ntet] = 0;
120 if (nr == -1) return -1;
121 nRet += nr;
122 --nUse;
123 SetVal(tetMap, x-dx, y, tsMap, 0);
124 }
125 break;
126 }
127 }
128 }
129 return nRet;
130 }
131 }
132 return nRet;
133 }
134
135 void output()
136 {
137 for (int y=10; y>=1; --y)
138 {
139 for (int x=10; x>=1; --x)
140 {
141 if (tetMap[y][x] <= 0) putchar('.');
142 else putchar(tetMap[y][x]+('A'-1));
143 }
144 putchar('\n');
145 }
146 }
147
148 #include <ctime>
149 int main()
150 {
151 Init();
152 int t = clock();
153 DFS();
154 t = clock()-t;
155 output();
156 printf("Time = %d\n", t);
157 return 0;
158 }
159