C++ 木棒拼正方形：算法详解与代码实现

题目描述

给定一些木棒的长度，判断能否用这些木棒（全部用完）拼成一个正方形。

输入格式

输入文件的第一行是一个整数 n 表示测试的组数，接下来 n 行表示每组的测试数据。每行的第一个数为 m(4 ≤ m ≤ 20)，接下来 m 个数 a_i(1 ≤ a_i ≤ 1000) 表示木棒的长度。

输出格式

对于每组测试数据，如果可以组成正方形输出'yes'，否则输出'no'。

样例 #1

样例输入 #1

3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

样例输出 #1

yes
no
yes

算法思路

1. 判断总长度是否能被 4 整除： 首先判断所有木棒的总长度是否能被 4 整除。如果不能整除，则无法拼成正方形，直接输出 'no'。
2. 计算正方形边长： 如果总长度能被 4 整除，则计算正方形的边长，即总长度除以 4。
3. 排序： 对所有木棒的长度进行降序排序，方便后面的递归搜索。
4. 深度优先搜索 (DFS)： 使用 DFS 算法尝试将木棒拼成正方形。DFS 过程如下：
   • 递归边界： 当所有木棒都已被使用（currentIndex == sticks.size()），且四个边的长度都相等（sides == 0），则找到了一种可行方案，返回 true。
   • 遍历所有木棒： 遍历每个木棒，尝试将其添加到四个边中的任意一边。
   • 剪枝： 如果当前木棒长度加上某一边的长度超过了正方形的边长，则跳过该边，尝试其他边。
   • 递归： 递归调用 DFS 函数，将当前木棒添加到当前选择的边上，继续尝试下一个木棒。
   • 回溯： 如果递归调用返回 false，则说明当前选择的边不可行，需要回溯到上一步，将当前木棒从选择的边上移除。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool dfs(vector<int>& sticks, int target, vector<int>& sides, int currentIndex) {
    if (currentIndex == sticks.size()) {
        return (sides == 0);
    }

    for (int i = 0; i < 4; i++) {
        if (sticks[currentIndex] + sides[i] <= target) {
            sides[i] += sticks[currentIndex];
            if (dfs(sticks, target, sides, currentIndex + 1)) {
                return true;
            }
            sides[i] -= sticks[currentIndex];
        }
    }

    return false;
}

bool canFormSquare(vector<int>& sticks) {
    int sum = 0;
    for (int i = 0; i < sticks.size(); i++) {
        sum += sticks[i];
    }

    if (sum % 4 != 0) {
        return false;
    }

    int target = sum / 4;

    vector<int> sides(4, 0);

    sort(sticks.rbegin(), sticks.rend());

    return dfs(sticks, target, sides, 0);
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int m;
        cin >> m;

        vector<int> sticks(m);
        for (int j = 0; j < m; j++) {
            cin >> sticks[j];
        }

        if (canFormSquare(sticks)) {
            cout << 'yes' << endl;
        } else {
            cout << 'no' << endl;
        }
    }

    return 0;
}

总结

这道题使用深度优先搜索 (DFS) 算法，通过递归的方式尝试将木棒拼成正方形。代码中使用了剪枝操作，避免了不必要的递归调用，提高了算法效率。