UVa 10364 - Square

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址
中文網址

判斷給出的棍子長度，可否連成正方形(每根都要用且不能折斷棍子)。

Solution

主要就是做回溯法，並提早排除不可能的。

一開始先排序由長的棍子開始組，可以減少回溯次數。
計算出正方形單邊的長度後，回溯時，只要長度超過單邊就可以不用進行遞迴了。每完成一個邊就將長度歸 0 ，重新開始組另一邊(只需要完成 3 個邊就可以確定了)，一方面紀錄使用了那些棍子。

Code

UVa 10364UVa 10364 - Square

#include<cstdio>
#include<algorithm>
using namespace std;

int side_length;//單邊長度
int stick[21];
bool used[21];
bool backtracking(int n, int len, int now, int idx);
int main()
{
    int Case;
    scanf("%d", &Case);
    while (Case--)
    {
        int n, sum = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &stick[i]);
            sum += stick[i];
        }
        //先排序減少回溯次數
        sort(stick, stick + n, [](const int& s1, const int& s2)->bool{return s1 > s2; });
        fill(used, used + n, false);
        side_length = sum / 4;//單邊長度

        if (sum % 4 || stick[0] > side_length)
            puts("no");
        else
            puts(backtracking(n, 0, 0, 0) ? "yes" : "no");
    }

    return 0;
}
bool backtracking(int n, int len, int now, int idx)//(棍子數,目前連接的長度,完成的邊數,紀錄做到哪根棍子)
{
    //完成一邊
    if (len == side_length)
    {
        len = idx = 0;
        now++;
        if (now == 3)
            return true;
    }

    for (int i = idx; i < n; i++)
    {
        if (!used[i])
        {
            if (len + stick[i] <= side_length)//提早排除長度超過的
            {
                used[i] = true;
                if (backtracking(n, len + stick[i], now, i + 1))
                    return true;

                used[i] = false;

                //待會就算用別根完成了現在這一邊，最後還是有邊無法完成
                if (len + stick[i] == side_length)
                    return false;
            }
        }
    }

    return false;
}