[USACO][Section 2.3][枚举] Zero Sum

题目大意

---

思路

---

代码

---

/*
ID: lujunda1
LANG: C++
PROG: zerosum
*/
#include
#include
#include
#include
using namespace std;

struct state
//结构体state用于存储式子。 
{
    char str[20];
};

bool check(char* str,int n)
//判断式子str的结果是否为0。 
{
    int len=n*2-1;
    int sum=0,op=1,temp=1;
    //sum式子临时的结果。
    //op当前运算数的符号。
    //temp当前运算数的大小。 
    for(int i=1;i<len;i++)
        if(i%2)
        {
            if(str[i]==' ')
            {
                temp*=10;
                continue;
            }
            sum+=temp*op;
            op=str[i]=='+'?1:-1;
            temp=0;
        }
        else
            temp+=str[i]-'0';
    return sum+temp*op==0?true:false;
    //temp*op为str的结果。 
}

void bfs(int n)
{
    queue q;
    state head;
    head.str[0]='1';
    head.str[1]='\0';
    q.push(head);
    int temp=1;
    while(++temp<=n)
    {
        int size=q.size();
        while(size--)
        {
            head=q.front();
            q.pop();
            head.str[temp*2-3]=' ';
            //按字典序，先' '，后'+'，最后'-'。 
            head.str[temp*2-2]='0'+temp;
            head.str[temp*2-1]='\0';
            q.push(head);
            head.str[temp*2-3]='+';
            q.push(head);
            head.str[temp*2-3]='-';
            q.push(head);
        }
    }
    while(q.size())
    {
        if(check(q.front().str,n))
            printf("%s\n",q.front().str);
        q.pop();
    }
}

int main()
{
    freopen("zerosum.in","r",stdin);
    freopen("zerosum.out","w",stdout);
    int n;
    scanf("%d",&n);
    bfs(n);
}