1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
| #include <cstdio>
#include <vector>
using namespace std;
const int N = 20, M = 2e3;
char g[N][N];
struct OP
{
int x, y;
char c;
};
vector<OP> op;
struct Node
{
int x, y;
int l, r, u, d;
};
vector<Node> p;
int n = 1 << 4, m = 1 << 10, top, ans[M], s[M];
int num(int x, int y)
{
return x * 16 + y + 1;
}
void init()
{
op.clear();
p.clear();
top = 0;
for (int i = 1; i <= m; i++)
s[i] = 0;
p.push_back({0, 0, m, 1, 0, 0});
for (int i = 1; i < m; i++)
p.push_back({0, i, i - 1, i + 1, i, i});
p.push_back({0, m, m - 1, 0, m, m});
}
void add(int &hd, int &tl, int x, int y)
{
int t = p.size();
p.push_back({x, y, hd, tl, y, p[y].d});
tl = p[hd].r = p[tl].l = p[y].d = p[p[y].d].u = t;
s[y]++;
}
void remove(int x)
{
p[p[x].l].r = p[x].r, p[p[x].r].l = p[x].l;
for (int i = p[x].d; i != x; i = p[i].d)
for (int j = p[i].r; j != i; j = p[j].r)
{
s[p[j].y]--;
p[p[j].d].u = p[j].u, p[p[j].u].d = p[j].d;
}
}
void resume(int x)
{
for (int i = p[x].u; i != x; i = p[i].u)
for (int j = p[i].l; j != i; j = p[j].l)
{
s[p[j].y]++;
p[p[j].d].u = j, p[p[j].u].d = j;
}
p[p[x].l].r = x, p[p[x].r].l = x;
}
bool dfs()
{
if (!p[0].r)
return true;
int t = p[0].r;
for (int i = p[0].r; i; i = p[i].r)
if (s[i] <= s[t])
t = i;
if (!t)
return false;
remove(t);
for (int i = p[t].d; i != t; i = p[i].d)
{
ans[++top] = p[i].x;
for (int j = p[i].r; j != i; j = p[j].r)
remove(p[j].y);
if (dfs())
return true;
for (int j = p[i].l; j != i; j = p[j].l)
resume(p[j].y);
top--;
}
resume(t);
return false;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
init();
for (int i = 0; i < n; i++)
scanf("%s", g[i]);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
{
int l = 0, r = n - 1;
if (g[i][j] != '-')
l = r = g[i][j] - 'A';
for (int k = l; k <= r; k++)
{
int hd = p.size(), tl = p.size();
add(hd, tl, op.size(), 256 * 0 + num(i, j));
add(hd, tl, op.size(), 256 * 1 + num(i, k));
add(hd, tl, op.size(), 256 * 2 + num(j, k));
add(hd, tl, op.size(), 256 * 3 + num(i / 4 * 4 + j / 4, k));
op.push_back((OP){i, j, (char)(k + 'A')});
}
}
dfs();
for (int i = 1; i <= top; i++)
g[op[ans[i]].x][op[ans[i]].y] = op[ans[i]].c;
for (int i = 0; i < n; i++)
puts(g[i]);
}
return 0;
}
|