P6996

zhylj · 2022-01-12 18:05:37 · 题解

考虑暴搜每个位置放哪个拼图，然后 \mathcal O(wh) Check，注意到由于题目的限制，角落上的拼图的位置是确定的；而边界上的拼图被确定在 n-2 个位置里，可以在内部枚举选择方案；剩下的位置再暴搜。这样情况就只剩下了 (n-2)!^4((n-2)^2)! 种，非常之少，随便实现就可以过了。

const int N = 50;

int k, w, h, n, W, H;
char str[N][N][N], ans[N][N];

void Output() {
    printf("%d %d\n", W, H);
    for(int i = 1; i <= H; ++i)
        printf("%s\n", ans[i] + 1);
}

bool Repl(int id, int pos_x, int pos_y, char c_bg, char c_ed) {
    std::vector <pii> vaild_pos;
    int mov_x = -h + (pos_x - 1) * h + 1, mov_y = -w + (pos_y - 1) * w + 1;
    bool up_b = true, dn_b = true, lf_b = true, ri_b = true;
    for(int y = w; y <= 2 * w - 1; ++y) {
        if(str[id][h - 1][y] != '.' || str[id][h][y] == '.') up_b = false;
        if(str[id][2 * h][y] != '.' || str[id][2 * h - 1][y] == '.') dn_b = false;
    }
    for(int x = h; x <= 2 * h - 1; ++x) {
        if(str[id][x][w - 1] != '.' || str[id][x][w] == '.') lf_b = false;
        if(str[id][x][2 * w] != '.' || str[id][x][2 * w - 1] == '.') ri_b = false;
    }
    if((up_b && pos_x != 1) || (dn_b && pos_x != n) ||
        (lf_b && pos_y != 1) || (ri_b && pos_y != n)) return false;
    for(int x = 1; x <= h * 3 - 2; ++x)
        for(int y = 1; y <= w * 3 - 2; ++y) {
            int nx = x + mov_x, ny = y + mov_y;
            if(str[id][x][y] != '.') {
                if(nx <= 0 || ny <= 0 || nx > H || ny > W || ans[nx][ny] != c_bg)
                    return false;
                vaild_pos.push_back(mkp(nx, ny));
            }
        }
    for(pii i : vaild_pos) {
        int x = i.fi, y = i.se;
        ans[x][y] = c_ed;
    }
    return true;
}

bool vis[N];
void Dfs(int cur_pos_x, int cur_pos_y) {
    if(cur_pos_x == n + 1) { Output(); exit(0); }
    for(int i = 1; i <= k; ++i) {
        if(!vis[i] && Repl(i, cur_pos_x, cur_pos_y, '.', i - 1 + 'A')) {
            vis[i] = true;
            Dfs(cur_pos_x + (cur_pos_y == n), cur_pos_y % n + 1);
            Repl(i, cur_pos_x, cur_pos_y, i - 1 + 'A', '.');
            vis[i] = false;
        }
    }
}

int main() {
    rd(k, w, h);
    n = lround(floor(sqrt(k)));
    W = w * n; H = h * n;
    for(int i = 1; i <= H; ++i)
        for(int j = 1; j <= W; ++j) ans[i][j] = '.';
    for(int i = 1; i <= k; ++i)
        for(int j = 1; j <= h * 3 - 2; ++j)
            scanf("%s", str[i][j] + 1);
    Dfs(1, 1);
    return 0;
}