0

我正在编写一个程序来查找是否可以用 N 根长度为 N 的棍子制作一个正方形。我使用过 Bitmask，因为它更容易用于我要放入的大量输入。出于某种原因，我的回溯代码没有返回任何内容，在这一行“位掩码 & (1 << vec[i])”中它永远不会进入。如果我使用了错误的函数，有人可以帮助我吗？我最近学到了这个，但我找不到信息。

PD：我不会说英语，抱歉我的语法和句法问题。

谢谢

// 10364 - Square.cpp: archivo de proyecto principal.
#include "stdafx.h"
#include <stdio.h>
#include <vector>

using namespace std;

vector<int> vec;
int bitmask,casos,palitos,suma,maximo;
bool analiza(int analizado,int lados)// lados =cantidad lados analizados, contador
{
    if (analizado==maximo)
    {
        analizado=0;
        lados++;
    }
    if(lados==4)
    {
        printf("yes\n");
        return true;
    }

        for (int i=0;i<palitos;i++)
        {
            if (!(bitmask & (1 << i)))
            {
                if (analizado+vec[i]<=maximo)
                {
                    bitmask | (1 << i);
                    if(analiza(analizado+1,lados))
                        return true;
                    bitmask & ~(1 << i);

                }
            }

        }
        return false;
        //prender: bitmask | (1 << indice)
        //apagar: bitmask & ~(1 << indice)
        /*comparar: bitmask & (1 << indice)*/
}
int main()
{
    freopen("in.txt","rt",stdin);
    freopen("out.txt","wt",stdout);

    scanf("%d\n",&casos);
    for(int i=0;i<casos;i++)
    {
        scanf("%d",&palitos);
        vec.clear();
        vec.resize(palitos);
        suma=0;
        for(int j=0;j<palitos;j++)
        {
            scanf("%d",&vec[j]);
            suma+=vec[j];
        }
        if(suma%4!=0)
            printf("no\n");
        else{
            bitmask=0;
            maximo=suma/4;
            analiza(0,0);
            }


    }


    return 0;
}
4

1 回答 1

2

您似乎从未初始化位掩码。如果位掩码恰好为 0，那么您将永远不会进入循环。这似乎是问题的一部分。
也(bitmask & (1 << i)可以简化为 '0' 因为位掩码为 0 并且您正在使用 bitwise and。因此，if可以消除整个条件，因为它总是评估为真。
此外，您似乎没有以正确的方式使用位掩码。您希望位掩码至少有一个位等于 1，因为当您and使用一些带有位掩码的向量时，您将只保留相关位。然后，如果您进行位移，您可以判断向量中有趣的位是打开还是关闭。

于 2012-10-23T04:21:41.547 回答