# 搭积木

小明最近喜欢搭数字积木，
一共有10块积木，每个积木上有一个数字，0~9。

搭积木规则：
每个积木放到其它两个积木的上面，并且一定比下面的两个积木数字小。
最后搭成4层的金字塔形，必须用完所有的积木。

下面是两种合格的搭法：
```	
			   0
			  1 2
			 3 4 5
			6 7 8 9
			
			   0
			  3 1
			 7 5 2
			9 8 6 4    
```			
请你计算这样的搭法一共有多少种？



## aop

### before

```cpp
#include <bits/stdc++.h>
using namespace std;
int row = 4, col;
int seq[5][8]; 
int tmp[11];
int cnt = 0;
bool used[10];

void change()
{ 
    int cur = 1;
    for (int i = 1; i <= row; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            seq[i][j] = tmp[cur++];
        }
    }
}

bool judge()
{ 
    for (int i = 1; i <= row - 1; ++i)
    {
        for (int j = 1; j <= i; ++j)
        {
            if (seq[i][j] > seq[i + 1][j] || seq[i][j] > seq[i + 1][j + 1])
                return false;
        }
    }
    return true;
}
int ans = 0;
```
### after

```cpp
int main()
{
    memset(used, false, sizeof(used));
    dfs(1);
    cout << cnt << endl;
    return 0;
}
```

## 答案

```cpp
void dfs(int idx)
{
    
    if (idx == 11)
    {
        change();
        if (judge())
        {
            cnt++;
            return;
        }
        return;
    }
    for (int i = 0; i <= 9; ++i)
    {
        if (!used[i])
        {
            tmp[idx] = i;
            used[i] = true;
            dfs(idx + 1);
            used[i] = false;
        }
    }
}
```
## 选项


### A

```cpp
void dfs(int idx)
{
    
    if (idx == 11)
    {
        change();
        if (judge())
        {
            cnt++;
            return;
        }
        return;
    }
    for (int i = 0; i <= 9; ++i)
    {
        if (!used[i])
        {
            tmp[idx] = i;
            used[i] = true;
            dfs(idx);
            used[i] = false;
        }
    }
}
```

### B

```cpp
void dfs(int idx)
{
    
    if (idx == 11)
    {
        change();
        if (judge())
        {
            cnt++;
            return;
        }
        return;
    }
    for (int i = 0; i <= 9; ++i)
    {
        if (!used[i])
        {
            tmp[idx] = i;
            used[i] = false;
            dfs(idx);
            used[i] = true;
        }
    }
}
```

### C

```cpp
void dfs(int idx)
{
    
    if (idx == 11)
    {
        change();
        if (judge())
        {
            cnt++;
            return;
        }
        return;
    }
    for (int i = 0; i <= 9; ++i)
    {
        if (!used[i])
        {
            tmp[idx] = i;
            used[i] = false;
            dfs(idx + 1);
            used[i] = true;
        }
    }
}
```
