#include "stdafx.h"#include <stack>#include <queue>#include <iostream>#include <cstdio>#include <cstdlib>using namespace std;int n = 0;typedef stack<int> Stack;typedef queue<int> Queue;void dfs(int level,Stack s, Queue buf, const int LEVEL);/* * 每一次递归都只有一个元素(level)入栈, 但是可能有0个元素出栈, 也可能有至少一个元素出栈 * @param level 当前规模            the scale of current sub-problem * @param s     当前子问题的栈       the stack of current sub-problem * @param buf   当前子问题的打印队列  the printing queue of current sub-problem * @param LEVEL 最大规模             the maximum scale of the problem */void dfs(int level,Stack s, Queue buf, const int LEVEL){    // By using "#pragma region xxx" direction, the code can appear more gracefully~#pragma region Termination of recursion    if (level == LEVEL)    {        // first we print all elements in the queue        buf.push(level);        while(!buf.empty())        {            cout<<buf.front()<<" ";            buf.pop();        }        // then we clear the stack        while(!s.empty())        {            cout << s.top()<<" ";            s.pop();        }        cout<<endl;        n++;        return;    }#pragma endregion 当level==LEVEL的时候递归停止    Queue tempQueue(buf);    s.push(level);    Stack tempStack(s);    /*     * 非常重要的步骤     * 把当前问题分解成若干子问题     * 必须考虑到所有可能的子问题, 如     * 1. push then no pop     * 2. push then pop 1     * 3. push then pop 2     *    ......     */    while(!s.empty())    {        buf.push(s.top());        s.pop();        dfs(level+1, s, buf, LEVEL);    }    dfs(level+1, tempStack, tempQueue, LEVEL);}int _tmain(int argc, _TCHAR* argv[]){    unsigned int cases;    int x;        scanf("%d", &cases);    while(cases--)    {            Stack s = Stack();        Queue q = Queue();        cin>>x;        dfs(1, s, q, x);        cout<<"the catalan number of "<<x<<" is "<<n<<endl;        n=0;    }    system("shutdown -s -t 60");}

#pragma once;class Result{private:    int* data;    int n;public:    Result(int _N):n(_N)    {        data = new int[2*n];        recover();    }    ~Result() {delete[] data;}    Result(const Result& src)    {        n = src.n;        data = new int[2*n];        for(int i=0; i<2*n; ++i)        {            data[i] = src[i];        }    }    int& operator[](int index)    {        return data[index];    }    const int& operator[] (int index) const    {        return data[index];    }    bool insert(int i, int level)    {        if (i<0 || i+level+1>2*n) return false;        if (data[i]==0 && data[i+level+1]==0)        {            data[i] = data[i+level+1] = level;            return true;        }        else return false;    }    void recover()    {        for (int i=0; i<2*n; ++i)        {            data[i] = 0;        }    }    Result& operator=(const Result& src)    {        delete[] data;        n = src.n;        data = new int[2*n];        for(int i=0; i<2*n; ++i)        {            data[i] = src[i];        }        return *this;    }    int size() const    {        return 2*n;    }    void print() const    {        for(int i=0; i<2*n; ++i)            printf_s("%d ", data[i]);        printf_s("\n");    }};

#include "stdafx.h"#include "Result.h"#include <stack>#include <queue>#include <list>#include <vector>using namespace std;void dfs(int level, Result res){    if (level<1)    {        res.print();        return;    }    Result temp = res;    for (int i=0; i<res.size()-level-1; ++i)    {        if (temp.insert(i, level))        {            dfs(level-1, temp);            temp = res;        }        else continue;    }}int _tmain(int argc, _TCHAR* argv){    int cases;    scanf_s("%d", &cases);    while (cases--)    {        int n;        scanf_s("%d", &n);        Result res = Result(n);        dfs(n, res);    }}