#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10;
const int MAXM = 1 << 9;
const int MAXK = 82;
int dp[MAXN][MAXM][MAXK][MAXN];// ¨¨¡À¨º¡ì¦Ì??¦Ì
//¦Ì¨²iDD ¦Ì¡À?¡ãDD¡Á¡ä¨¬??aj ¡¤???¨¢?K??¨¤¡Á ¨°?DD¨®DN??
int from[MAXN][MAXM][MAXK][MAXN];// ¡ä¨®??¨¤?¨¤¡ä
int sum[MAXM];//¡Á¡ä¨¬??ak ¨®D?¨¤¨¦¨´¨¤¡Á
void work() {
int n, m, k;
std::cin >> n >> m >> k;
int result = INT_MAX;
int idx = 91;
for (int i = 0; i < (1 << m); i++) {
int val = dp[n][i][k][m] + 3 * sum[i];
val -= (i & 1) + (i >> (m - 1) & 1);
if (val < result) {
result = val;
idx = i;
}
}
cout << 8 * k - result << endl;
for (int i = n; i >= 1; i--) {
for (int j = 0; j < m; j++) {
if (idx >> j & 1) {
cout << "*";
}
else {
cout << ".";
}
} cout << endl;
k -= sum[idx];
idx = from[i][idx][k][m];
}
}
unsigned _builtin_popcount(unsigned u) {
u = (u & 0x55555555) + ((u >> 1) & 0x55555555);
u = (u & 0x33333333) + ((u >> 2) & 0x33333333);
u = (u & 0x0F0F0F0F) + ((u >> 4) & 0x0F0F0F0F);
u = (u & 0x00FF00FF) + ((u >> 8) & 0x00FF00FF);
u = (u & 0x0000FFFF) + ((u >> 16) & 0x0000FFFF);
return u;
}
int main() {
for (int i = 0; i < (1 << 9); i++) {
sum[i] = _builtin_popcount(i);
}
memset(dp, 0x3f, sizeof dp);
for (int i = 1; i <= 9; i++) {
dp[0][(1 << i) - 1][0][i] = 0;
for (int j = 1; j <= 9; j++) {
for (int now = 0; now < (1 << i); now++) {
for (int last = 0; last < (1 << i); last++) {
for (int w = 0; w < (j - 1) * i + 1; w++) {
int new_k = w + sum[now];
int val = dp[j - 1][last][w][i];
if (j > 1) {
//¨®?¨¦?¨°?DD¦Ì?1¡À?¡Á
val += sum[now & last] * 2 + sum[now & (last >> 1)] * 2
+ sum[now & (last << 1)] * 2;
}
else {
//¨®?¨¦?¡À???¦Ì?1¡À?¡Á
val += sum[now] * 3;
}
val += sum[now & (now >> 1)] * 2;//¡Á¨®¨®¨°
val += (now & 1) * 2 + ((now >> (i - 1)) & 1) * 2;//¡À???
if (dp[j][now][new_k][i] > val) {
dp[j][now][new_k][i] = val;
from[j][now][new_k][i] = last;
}
}
}
}
}
}
int T; std::cin >> T;
while (T--) {
work();
}
return 0;
}
全部评论
(0) 回帖