【原題見
這里】
很明顯的精確覆蓋的模型，12個零件，再加上它們經過旋轉、翻轉后的不同形狀，共60種，每種又可以放在不同的位置（只看最左上的那個珠子）一種零件的一種位置就是一行。列（限制）有兩種：每個格子只能放一個（55列），以及每個零件（注意是每個零件，不是每種零件）只能用一次（12列），共67列。預先放的那些零件可以看成預先選中的行。然后DLX精確覆蓋即可。
下面是DLX精確覆蓋的幾個易疵點：
（1）整個矩陣的行數和列數不能疵（比如本題是1644行，67列）；
（2）注意init_d()、add_node(int, int)、delcol(int)、resucol(int)中的一些細節：
【1】init_d()中，是否把m寫成了n；
【2】add_node(int, int)中，是否寫了cols[c]++；
【3】delcol(int)和resucol(int)中，變量有木有疵（比如把i寫成j之類的），另外是否對cols進行了處理；
（3）如果有一些行預先被選中，注意在刪掉這些行的時候是否刪光，不要漏了行頭（rowh）；
（4）注意區分行號、列號和結點下標，delcol(int x)和resucol(int x)中的參數x一定是列號，而記錄可行解的res數組里存放的一定是行號；
（5）結點的行、列號均從1開始（第0行、第0列有特殊意義）；
（6）如果有多組數據，檢查在每組數據之前是否將所有數組初始化；
本題代碼：
#include <iostream>
#include <stdio.h>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define set(i, j, x, y) PX[i][j] = x; PY[i][j] = y;
const int S = 10, n = 1644, m = 67, T = 60, INF = ~0U >> 2;;
const int LL[12] = {0, 4, 6, 14, 15, 19, 27, 31, 39, 47, 48, 52}, RR[12] = {3, 5, 13, 14, 18, 26, 30, 38, 46, 47, 51, 59};
const char SSS[T + 1] = "AAAABBCCCCCCCCDEEEEFFFFFFFFGGGGHHHHHHHHIIIIIIIIJKKKKLLLLLLLL";
struct dlnode {
int r, c, U, D, L, R;
} d[(n + 1) * (m + 1)];
int rowh[n + 1], cols[m + 1], nodes, PX[T][5], PY[T][5], len[T], No[S][S], pos[n + 1][3], _pos[T][S][S], res[n], res_len;
char a[S][S];
bool vst[12];
void init_d()
{
re3(i, 0, m) {d[i].U = d[i].D = i; d[i].L = i - 1; d[i].R = i + 1;} d[0].L = m; d[m].R = 0; nodes = m;
re1(i, n) rowh[i] = -1;
re1(i, m) cols[i] = 0;
}
void add_node(int r, int c)
{
cols[c]++; d[++nodes].r = r; d[nodes].c = c; d[nodes].U = d[c].U; d[nodes].D = c; d[c].U = nodes; d[d[nodes].U].D = nodes;
int rh = rowh[r]; if (rh == -1) d[nodes].L = d[nodes].R = rowh[r] = nodes; else {
d[nodes].L = d[rh].L; d[nodes].R = rh; d[rh].L = nodes; d[d[nodes].L].R = nodes;
}
}
void init()
{
freopen("zhzyx.in", "r", stdin);
char ch;
re(i, S) {
re(j, i+1) a[i][j] = getchar();
ch = getchar();
}
fclose(stdin);
}
void delLR(int x)
{
d[d[x].L].R = d[x].R; d[d[x].R].L = d[x].L;
}
void resuLR(int x)
{
d[d[x].L].R = d[d[x].R].L = x;
}
void delUD(int x)
{
d[d[x].U].D = d[x].D; d[d[x].D].U = d[x].U;
}
void resuUD(int x)
{
d[d[x].U].D = d[d[x].D].U = x;
}
void delcol(int x)
{
delLR(x); for (int i=d[x].D; i != x; i=d[i].D) for (int j=d[i].R; j != i; j=d[j].R) {cols[d[j].c]--; delUD(j);}
}
void resucol(int x)
{
for (int i=d[x].U; i != x; i=d[i].U) for (int j=d[i].L; j != i; j=d[j].L) {resuUD(j); cols[d[j].c]++;} resuLR(x);
}
void prepare()
{
init_d();
len[0] = 3; set(0, 0, 0, 0); set(0, 1, 0, 1); set(0, 2, 1, 0);
len[1] = 3; set(1, 0, 0, 0); set(1, 1, 0, 1); set(1, 2, 1, 1);
len[2] = 3; set(2, 0, 0, 0); set(2, 1, 1, 0); set(2, 2, 1, 1);
len[3] = 3; set(3, 0, 0, 0); set(3, 1, 1, 0); set(3, 2, 1, -1);
len[4] = 4; set(4, 0, 0, 0); set(4, 1, 0, 1); set(4, 2, 0, 2); set(4, 3, 0, 3);
len[5] = 4; set(5, 0, 0, 0); set(5, 1, 1, 0); set(5, 2, 2, 0); set(5, 3, 3, 0);
len[6] = 4; set(6, 0, 0, 0); set(6, 1, 0, 1); set(6, 2, 0, 2); set(6, 3, 1, 0);
len[7] = 4; set(7, 0, 0, 0); set(7, 1, 0, 1); set(7, 2, 0, 2); set(7, 3, 1, 2);
len[8] = 4; set(8, 0, 0, 0); set(8, 1, 1, 0); set(8, 2, 1, 1); set(8, 3, 1, 2);
len[9] = 4; set(9, 0, 0, 0); set(9, 1, 1, 0); set(9, 2, 1, -1); set(9, 3, 1, -2);
len[10] = 4; set(10, 0, 0, 0); set(10, 1, 0, 1); set(10, 2, 1, 0); set(10, 3, 2, 0);
len[11] = 4; set(11, 0, 0, 0); set(11, 1, 0, 1); set(11, 2, 1, 1); set(11, 3, 2, 1);
len[12] = 4; set(12, 0, 0, 0); set(12, 1, 1, 0); set(12, 2, 2, 0); set(12, 3, 2, 1);
len[13] = 4; set(13, 0, 0, 0); set(13, 1, 1, 0); set(13, 2, 2, 0); set(13, 3, 2, -1);
len[14] = 4; set(14, 0, 0, 0); set(14, 1, 0, 1); set(14, 2, 1, 0); set(14, 3, 1, 1);
len[15] = 5; set(15, 0, 0, 0); set(15, 1, 1, 0); set(15, 2, 2, 0); set(15, 3, 2, 1); set(15, 4, 2, 2);
len[16] = 5; set(16, 0, 0, 0); set(16, 1, 1, 0); set(16, 2, 2, 0); set(16, 3, 2, -1); set(16, 4, 2, -2);
len[17] = 5; set(17, 0, 0, 0); set(17, 1, 0, 1); set(17, 2, 0, 2); set(17, 3, 1, 0); set(17, 4, 2, 0);
len[18] = 5; set(18, 0, 0, 0); set(18, 1, 0, 1); set(18, 2, 0, 2); set(18, 3, 1, 2); set(18, 4, 2, 2);
len[19] = 5; set(19, 0, 0, 0); set(19, 1, 0, 1); set(19, 2, 0, 2); set(19, 3, 0, 3); set(19, 4, 1, 1);
len[20] = 5; set(20, 0, 0, 0); set(20, 1, 0, 1); set(20, 2, 0, 2); set(20, 3, 0, 3); set(20, 4, 1, 2);
len[21] = 5; set(21, 0, 0, 0); set(21, 1, 1, -1); set(21, 2, 1, 0); set(21, 3, 1, 1); set(21, 4, 1, 2);
len[22] = 5; set(22, 0, 0, 0); set(22, 1, 1, -2); set(22, 2, 1, -1); set(22, 3, 1, 0); set(22, 4, 1, 1);
len[23] = 5; set(23, 0, 0, 0); set(23, 1, 1, 0); set(23, 2, 1, 1); set(23, 3, 2, 0); set(23, 4, 3, 0);
len[24] = 5; set(24, 0, 0, 0); set(24, 1, 1, 0); set(24, 2, 1, -1); set(24, 3, 2, 0); set(24, 4, 3, 0);
len[25] = 5; set(25, 0, 0, 0); set(25, 1, 1, 0); set(25, 2, 2, 0); set(25, 3, 2, 1); set(25, 4, 3, 0);
len[26] = 5; set(26, 0, 0, 0); set(26, 1, 1, 0); set(26, 2, 2, 0); set(26, 3, 2, -1); set(26, 4, 3, 0);
len[27] = 5; set(27, 0, 0, 0); set(27, 1, 0, 1); set(27, 2, 0, 2); set(27, 3, 1, 0); set(27, 4, 1, 2);
len[28] = 5; set(28, 0, 0, 0); set(28, 1, 1, 0); set(28, 2, 1, 1); set(28, 3, 0, 2); set(28, 4, 1, 2);
len[29] = 5; set(29, 0, 0, 0); set(29, 1, 0, 1); set(29, 2, 1, 0); set(29, 3, 2, 0); set(29, 4, 2, 1);
len[30] = 5; set(30, 0, 0, 0); set(30, 1, 0, 1); set(30, 2, 1, 1); set(30, 3, 2, 0); set(30, 4, 2, 1);
len[31] = 5; set(31, 0, 0, 0); set(31, 1, 0, 1); set(31, 2, 0, 2); set(31, 3, 1, 0); set(31, 4, 1, 1);
len[32] = 5; set(32, 0, 0, 0); set(32, 1, 0, 1); set(32, 2, 0, 2); set(32, 3, 1, 1); set(32, 4, 1, 2);
len[33] = 5; set(33, 0, 0, 0); set(33, 1, 0, 1); set(33, 2, 1, 0); set(33, 3, 1, 1); set(33, 4, 1, 2);
len[34] = 5; set(34, 0, 0, 0); set(34, 1, 0, 1); set(34, 2, 1, -1); set(34, 3, 1, 0); set(34, 4, 1, 1);
len[35] = 5; set(35, 0, 0, 0); set(35, 1, 0, 1); set(35, 2, 1, 0); set(35, 3, 1, 1); set(35, 4, 2, 0);
len[36] = 5; set(36, 0, 0, 0); set(36, 1, 0, 1); set(36, 2, 1, 0); set(36, 3, 1, 1); set(36, 4, 2, 1);
len[37] = 5; set(37, 0, 0, 0); set(37, 1, 1, 0); set(37, 2, 1, 1); set(37, 3, 2, 0); set(37, 4, 2, 1);
len[38] = 5; set(38, 0, 0, 0); set(38, 1, 1, -1); set(38, 2, 1, 0); set(38, 3, 2, -1); set(38, 4, 2, 0);
len[39] = 5; set(39, 0, 0, 0); set(39, 1, 0, 1); set(39, 2, 0, 2); set(39, 3, 1, 2); set(39, 4, 1, 3);
len[40] = 5; set(40, 0, 0, 0); set(40, 1, 0, 1); set(40, 2, 0, 2); set(40, 3, 1, -1); set(40, 4, 1, 0);
len[41] = 5; set(41, 0, 0, 0); set(41, 1, 0, 1); set(41, 2, 1, 1); set(41, 3, 1, 2); set(41, 4, 1, 3);
len[42] = 5; set(42, 0, 0, 0); set(42, 1, 0, 1); set(42, 2, 1, -2); set(42, 3, 1, -1); set(42, 4, 1, 0);
len[43] = 5; set(43, 0, 0, 0); set(43, 1, 1, 0); set(43, 2, 2, 0); set(43, 3, 2, 1); set(43, 4, 3, 1);
len[44] = 5; set(44, 0, 0, 0); set(44, 1, 1, 0); set(44, 2, 2, -1); set(44, 3, 2, 0); set(44, 4, 3, -1);
len[45] = 5; set(45, 0, 0, 0); set(45, 1, 1, 0); set(45, 2, 1, 1); set(45, 3, 2, 1); set(45, 4, 3, 1);
len[46] = 5; set(46, 0, 0, 0); set(46, 1, 1, -1); set(46, 2, 1, 0); set(46, 3, 2, -1); set(46, 4, 3, -1);
len[47] = 5; set(47, 0, 0, 0); set(47, 1, 1, -1); set(47, 2, 1, 0); set(47, 3, 1, 1); set(47, 4, 2, 0);
len[48] = 5; set(48, 0, 0, 0); set(48, 1, 1, 0); set(48, 2, 1, 1); set(48, 3, 2, 1); set(48, 4, 2, 2);
len[49] = 5; set(49, 0, 0, 0); set(49, 1, 1, -1); set(49, 2, 1, 0); set(49, 3, 2, -2); set(49, 4, 2, -1);
len[50] = 5; set(50, 0, 0, 0); set(50, 1, 0, 1); set(50, 2, 1, 1); set(50, 3, 1, 2); set(50, 4, 2, 2);
len[51] = 5; set(51, 0, 0, 0); set(51, 1, 0, 1); set(51, 2, 1, -1); set(51, 3, 1, 0); set(51, 4, 2, -1);
len[52] = 5; set(52, 0, 0, 0); set(52, 1, 0, 1); set(52, 2, 0, 2); set(52, 3, 0, 3); set(52, 4, 1, 0);
len[53] = 5; set(53, 0, 0, 0); set(53, 1, 0, 1); set(53, 2, 0, 2); set(53, 3, 0, 3); set(53, 4, 1, 3);
len[54] = 5; set(54, 0, 0, 0); set(54, 1, 1, -3); set(54, 2, 1, -2); set(54, 3, 1, -1); set(54, 4, 1, 0);
len[55] = 5; set(55, 0, 0, 0); set(55, 1, 1, 0); set(55, 2, 1, 1); set(55, 3, 1, 2); set(55, 4, 1, 3);
len[56] = 5; set(56, 0, 0, 0); set(56, 1, 0, 1); set(56, 2, 1, 0); set(56, 3, 2, 0); set(56, 4, 3, 0);
len[57] = 5; set(57, 0, 0, 0); set(57, 1, 0, 1); set(57, 2, 1, 1); set(57, 3, 2, 1); set(57, 4, 3, 1);
len[58] = 5; set(58, 0, 0, 0); set(58, 1, 1, 0); set(58, 2, 2, 0); set(58, 3, 3, 0); set(58, 4, 3, 1);
len[59] = 5; set(59, 0, 0, 0); set(59, 1, 1, 0); set(59, 2, 2, 0); set(59, 3, 3, -1); set(59, 4, 3, 0);
int No0 = 0, x0, y0, z; re(i, S) re(j, i+1) No[i][j] = ++No0;
bool ff;
No0 = 0; re(i, T) re(x, S) re(y, x+1) {
ff = 1; re(j, len[i]) {
x0 = x + PX[i][j]; y0 = y + PY[i][j];
if (x0 < 0 || x0 >= S || y0 < 0 || y0 >= S || x0 < y0) {ff = 0; break;}
}
if (ff) {
No0++; pos[No0][0] = i; pos[No0][1] = x; pos[No0][2] = y; _pos[i][x][y] = No0;
re(j, len[i]) {x0 = x + PX[i][j]; y0 = y + PY[i][j]; add_node(No0, No[x0][y0]);} add_node(No0, 55 + SSS[i] - 64);
}
}
re(i, 12) vst[i] = 0;
int _x, rh;
re(x, S) re(y, x+1) if (a[x][y] != '.') {
z = a[x][y] - 65;
if (!vst[z]) {
vst[z] = 1;
re3(i, LL[z], RR[z]) {
ff = 1; re(j, len[i]) {
x0 = x + PX[i][j]; y0 = y + PY[i][j];
if (x0 < 0 || x0 >= S || y0 < 0 || y0 >= S || x0 < y0 || a[x0][y0] != a[x][y]) {ff = 0; break;}
}
if (ff) {
_x = _pos[i][x][y]; rh = rowh[_x]; delcol(d[rh].c);
for (int j=d[rh].R; j != rh; j=d[j].R) delcol(d[j].c);
break;
}
}
}
}
}
bool dfs(int dep)
{
if (!d[0].R) {res_len = dep; return 1;}
int mins = INF, c0; for (int i=d[0].R; i; i=d[i].R) if (!cols[i]) return 0; else if (cols[i] < mins) {mins = cols[i]; c0 = i;}
delcol(c0);
for (int i=d[c0].D; i != c0; i=d[i].D) {
for (int j=d[i].R; j != i; j=d[j].R) {delcol(d[j].c);}
res[dep] = d[i].r; if (dfs(dep + 1)) return 1;
for (int j=d[i].L; j != i; j=d[j].L) resucol(d[j].c);
}
resucol(c0);
return 0;
}
void solve()
{
int x, y, z;
if (dfs(0)) {
re(i, res_len) {
z = pos[res[i]][0]; x = pos[res[i]][1]; y = pos[res[i]][2];
re(j, len[z]) a[x + PX[z][j]][y + PY[z][j]] = SSS[z];
}
} else res_len = -1;
}
void pri()
{
freopen("zhzyx.out", "w", stdout);
if (res_len == -1) puts("No solution"); else re(i, S) {re(j, i+1) putchar(a[i][j]); puts("");}
fclose(stdout);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}