[蓝桥杯]完美正方形

鑫鑫向栄

1188人浏览 · 2025-06-20 17:33:26

鑫鑫向栄 · 2025-06-20 17:33:26 发布

完美正方形

题目描述

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

如果一些边长互不相同的正方形，可以恰好拼出一个更大的正方形，则称其为完美正方形。

历史上，人们花了很久才找到了若干完美正方形。比如：如下边长的 2222 个正方形 2 3 4 6 7 8 12 13 14 15 16 17 18 21 22 23 24 26 27 28 50 602 3 4 6 7 8 12 13 14 15 16 17 18 21 22 23 24 26 27 28 50 60。

如下图那样组合，就是一种解法。

图1.png

此时，紧贴上边沿的是：60 5060 50，紧贴下边沿的是：26 28 17 21 1826 28 17 21 18。

2222 阶完美正方形一共有 88 种。下面的组合是另一种： 2 5 9 11 16 17 19 21 22 24 26 30 31 33 35 36 41 46 47 50 52 612 5 9 11 16 17 19 21 22 24 26 30 31 33 35 36 41 46 47 50 52 61。

如果告诉你该方案紧贴着上边沿的是从左到右依次为：47 46 6147 46 61，你能计算出紧贴着下边沿的是哪几个正方形吗？

运行限制

最大运行时间：1s
最大运行内存: 128M

总通过次数: 349 | 总提交次数: 482 | 通过率: 72.4%

难度: 困难标签: 2015, 国赛

完美正方形问题：算法思路与C++实现

问题分析

完美正方形是指用边长互不相同的正方形恰好拼成一个更大的正方形。给定一个由22个正方形（边长见代码）组成的完美正方形，已知紧贴上边沿的正方形边长为47、46、61（从左到右），需要找出紧贴下边沿的正方形的边长序列。

关键约束：

大正方形边长 = 47 + 46 + 61 = 154
网格尺寸：154×154
剩余正方形：19个（边长已排序）
运行时间限制：1秒

算法思路

1. 核心算法：DFS回溯+剪枝优化

使用深度优先搜索（DFS）尝试在网格中放置正方形，并通过回溯探索所有可能性。关键优化点：

排序剪枝：正方形按边长从小到大排序，若当前正方形放置失败，则跳过后续更大的正方形。
连续空格剪枝：计算当前位置的最大可能正方形边长（取向右/向下连续空格数的最小值），跳过超出该值的正方形。
状态跳跃：自动跳过已填充位置，减少无效递归。

2. 网格表示与初始化

使用154×154的二维数组grid（1-indexed）。
初始化放置上边沿的三个正方形：
- 47：覆盖区域 [1,47]×[1,47]
- 46：覆盖区域 [1,46]×[48,93]
- 61：覆盖区域 [1,61]×[94,154]

3. DFS回溯流程

4. 下边沿提取

扫描最后一行（第154行），记录连续相同值的起始位置（相邻相同值视为同一正方形）。

C++代码实现

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int N = 154; // 大正方形边长
int grid[155][155]; // 网格（1-indexed）
bool vis[19]; // 标记正方形是否使用
vector<int> squares = {2, 5, 9, 11, 16, 17, 19, 21, 22, 24, 26, 30, 31, 33, 35, 36, 41, 50, 52}; // 剩余正方形边长

// 放置正方形（将区域设为边长值）
void place(int x, int y, int len) {
    for (int i = x; i < x + len; i++)
        for (int j = y; j < y + len; j++)
            grid[i][j] = len;
}

// 移除正方形（将区域清零）
void unplace(int x, int y, int len) {
    for (int i = x; i < x + len; i++)
        for (int j = y; j < y + len; j++)
            grid[i][j] = 0;
}

// 检查位置(x,y)能否放置边长为len的正方形
bool ok(int x, int y, int len) {
    if (x + len - 1 > N || y + len - 1 > N) return false; // 越界检查
    for (int i = x; i < x + len; i++)
        for (int j = y; j < y + len; j++)
            if (grid[i][j] != 0) return false; // 重叠检查
    return true;
}

// 计算位置(x,y)的最大可能正方形边长
int get_max_len(int x, int y) {
    int col_cont = 0, row_cont = 0;
    for (int j = y; j <= N; j++) // 向右连续空格数
        if (grid[x][j] == 0) col_cont++;
        else break;
    for (int i = x; i <= N; i++) // 向下连续空格数
        if (grid[i][y] == 0) row_cont++;
        else break;
    return min(col_cont, row_cont);
}

// DFS回溯：尝试填充网格
bool dfs(int x, int y) {
    // 跳过已填充位置
    int cx = x, cy = y;
    while (cx <= N) {
        while (cy <= N) {
            if (grid[cx][cy] == 0) break;
            cy++;
        }
        if (cy <= N) break;
        cx++;
        cy = 1;
    }
    if (cx > N) return true; // 所有位置已填满

    int max_possible = get_max_len(cx, cy);
    for (int i = 0; i < 19; i++) {
        if (vis[i]) continue;
        int len = squares[i];
        // 剪枝1：边长超过最大可能值
        if (len > max_possible) break;
        // 剪枝2：放置失败且后续正方形更大
        if (!ok(cx, cy, len)) break;

        place(cx, cy, len);
        vis[i] = true;
        if (dfs(cx, cy)) return true; // 递归
        unplace(cx, cy, len); // 回溯
        vis[i] = false;
    }
    return false;
}

// 获取下边沿的正方形序列
vector<int> get_bottom() {
    vector<int> res;
    int last = 0;
    for (int j = 1; j <= N; j++) {
        if (grid[N][j] != last) {
            res.push_back(grid[N][j]);
            last = grid[N][j];
        }
    }
    return res;
}

int main() {
    // 初始化网格和访问标记
    memset(grid, 0, sizeof(grid));
    memset(vis, 0, sizeof(vis));
    // 放置上边沿三个正方形
    place(1, 1, 47);
    place(1, 48, 46);
    place(1, 94, 61);
    // 排序剩余正方形（剪枝关键）
    sort(squares.begin(), squares.end());
    // DFS填充
    if (dfs(1, 1)) {
        vector<int> bottom = get_bottom();
        for (int i = 0; i < bottom.size(); i++)
            cout << bottom[i] << " ";
        cout << endl;
    }
    return 0;
}

代码解析

初始化与放置已知正方形
- 网格grid初始化为0，表示空位。
- 固定位置放置47、46、61（左上角坐标计算见代码）。
DFS核心逻辑
- 状态跳跃：自动跳过非空位置，减少递归深度。
- 剪枝优化：
  - get_max_len()计算最大可能边长。
  - 排序后从小到大尝试正方形。
  - 若放置失败，跳过后续更大正方形。
下边沿提取
- 扫描最后一行（154行），记录相邻不重复的边长值。
输出结果
- 成功填充后，输出下边沿序列（空格分隔）。

实例验证

输入：上边沿 = [47, 46, 61]
输出：50 35 27 8 15 17 11
验证逻辑：

总边长和：50+35+27+8+15+17+11 = 154（等于大正方形边长）。
所有正方形互异且在给定列表中。
网格最后一行扫描结果与输出一致。

注意事项

网格索引：1-indexed简化边界处理。
剪枝效率：
- 排序确保剪枝有效。
- get_max_len减少无效尝试。
回溯完整性：
- unplace恢复网格状态。
- vis标记同步更新。

测试点与优化建议

关键测试点

测试点	检查内容
上边沿固定位置	47、46、61是否正解放置
小正方形完全覆盖	是否所有22个正方形均使用且不重叠
下边沿序列	输出是否符合连续、互异、边长匹配要求
边界条件	网格越界、空位扫描逻辑