题解：拼图组合成正方形问题

问题描述

给定 $1$ 到 $5$ 个拼图块，每个拼图块由 $0$ 和 $1$ 组成的矩阵表示（$1$ 表示实体部分，$0$ 表示空白）。要求在不旋转和翻转的情况下，将这些拼图块组合成一个 $4 \times 4$ 的正方形。若能成功组合，输出具体排列方式；否则输出 $No solution possible$。

算法思路

采用**深度优先搜索（DFS）**算法：

1. 输入处理：读取每个拼图块的尺寸 $n_i \times m_i$ 和形状矩阵 $a_i$。
2. DFS 搜索：
   • 对于每个拼图块，尝试所有可能的放置位置 $(i,j)$
   • 检查该位置是否能放置（不重叠且不越界）
   • 若能放置，则递归处理下一个拼图块
   • 若所有拼图块放置完毕且填满 $4 \times 4$ 网格，则记录解
3. 回溯机制：当某条路径无法找到解时，撤销当前拼图块的放置，尝试其他位置。

复杂度分析

• 时间复杂度：$O(\prod_{k=1}^T (4-n_k+1)(4-m_k+1))$（最坏情况需遍历所有可能组合）
• 空间复杂度：$O(30 \times 10 \times 10)$（存储拼图形状和当前布局）

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

int T; // 拼图块数量
int n[30], m[30]; // 各拼图块尺寸
int a[30][10][10]; // 拼图形状存储
int b[10][10]; // 当前布局
int jg; // 解决方案标记

void dfs(int x) {
    if (jg) return; // 已找到解则终止
    
    if (x == T) { // 所有拼图块已放置
        for (int i = 0; i < 4; i++)
            for (int j = 0; j < 4; j++)
                if (!b[i][j]) return; // 未填满则返回
        
        jg = 1;
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++)
                printf("%d", b[i][j]);
            printf("\n");
        }
        printf("\n");
        return;
    }

    // 尝试所有可能放置位置
    for (int i = 0; i <= 4 - n[x]; i++) {
        for (int j = 0; j <= 4 - m[x]; j++) {
            int can_place = 1;
            // 检查是否可以放置
            for (int l = 0; l < n[x] && can_place; l++)
                for (int h = 0; h < m[x]; h++)
                    if (a[x][l][h] && b[i+l][j+h]) {
                        can_place = 0;
                        break;
                    }
            
            if (can_place) {
                // 放置拼图块
                for (int l = 0; l < n[x]; l++)
                    for (int h = 0; h < m[x]; h++)
                        if (a[x][l][h])
                            b[i+l][j+h] = x + 1;
                
                dfs(x + 1); // 处理下一个拼图块
                
                // 回溯
                for (int l = 0; l < n[x]; l++)
                    for (int h = 0; h < m[x]; h++)
                        if (a[x][l][h])
                            b[i+l][j+h] = 0;
            }
        }
    }
}

int main() {
    while (1) {
        scanf("%d", &T);
        if (!T) break;
        
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for (int i = 0; i < T; i++) {
            scanf("%d%d", &n[i], &m[i]);
            for (int j = 0; j < n[i]; j++)
                for (int k = 0; k < m[i]; k++)
                    scanf("%1d", &a[i][j][k]);
        }
        
        jg = 0;
        dfs(0);
        if (!jg) printf("No solution possible\n\n");
    }
    return 0;
}

关键点说明

1. DFS 参数：$x$ 表示当前正在处理的第 $x$ 个拼图块（从 $0$ 开始计数）
2. 放置检查：通过双重循环检查目标区域是否全为 $0$
3. 回溯操作：在递归返回时需要将当前拼图块的影响清除
4. 终止条件：当 $b$ 数组中所有 $4 \times 4$ 位置均不为 $0$ 时找到有效解

示例分析

对于输入：

2
2 2
11
11
2 2
11
11

程序将输出：

1111
1111
0000
0000

No solution possible

说明第一个解不满足全填充条件，最终无解。