幸運三角形 南陽acm491（dfs）

幸運三角形

時間限制：1000 ms ?|? 內存限制：65535 KB

難度：3

描述

? ? ? ? 話說有這么一個圖形，只有兩種符號組成（‘+’或者‘-’），圖形的最上層有n個符號，往下個數依次減一，形成倒置的金字塔形狀，除第一層外（第一層為所有可能情況），每層形狀都由上層決定，相鄰的符號相同，則下層的符號為‘+’，反之，為‘-’;如下圖所示（n = 3 時的兩種情況)：

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

如果圖中的兩種符號個數相同，那這個三角形就是幸運三角形，如上圖中的圖（2）.

輸入

有多組測試數據（少于20組）。
每行含一個整數n（0<n<20)。

輸出

輸出相應的幸運三角形個數。

樣例輸入

3
4

樣例輸出

4
6

來源

原創

上傳者

ACM_楊延璽

算法思想：把+看成1，把-看成0，具體看代碼實現

#include<stdio.h>
int b[25][25];
int n,ans;
void dfs(int z,int x,int y)    //x = 0（表示'-'）,y = 1（表示'+'）,
{
    int x1,y1;
    if(z == n)
    {
        if(x == y)
        {
            ans++;
            return;
        }
        return;
    }
    for(int k=0; k<=1; k++)
    {
        x1 = x,y1 = y;
        b[0][z] = k;    //用來存儲三角形第一行
        b[0][z]>0 ? y1++ : x1++;
        for(int i=1,j=z-1; j>=0; i++,j--)    //用來判斷上一行相鄰數
        {
            b[i][j] = b[i-1][j] ^ b[i-1][j+1];    //(1^0 || 0^1 == 0); (1^1 || 0^0 == 1)
            b[i][j]>0 ? y1++ : x1++;
        }
        dfs(z+1,x1,y1);
    }
}
int main()
{
    int a[25];
    a[0] = 0;
    for(int i=1; i<=20; i++)    //a[25]用來存儲n三角形為偶數還是奇數
        a[i] = (a[i-1]+i);
    while(scanf("%d",&n)!=EOF)
    {
        ans = 0;
        if(a[n]%2 == 0)    //為偶數時才可能有幸運三角形
            dfs(0,0,0);
        printf("%d\n",ans);
    }
    return 0;
}

?