fzu 2030 括號問題（DFS）

fzu 2030 括號問題（DFS）

Problem 2030 括號問題

Accept: 413 Submit: 804
Time Limit: 1000 mSec Memory Limit : 32768 KB

Problem Description

給出一個字符串，其中包括3種字符: ‘(‘, ‘)’, ‘?’.其中?表示這個字符可以是’(‘也可以是’)’. 現在給出字符串S,你可以在’?’處填寫’(‘ 或者 ‘)’，當然隨意填寫得到的序列可能是括號不匹配的。例如”(?”，如果你填寫’(‘那麼”((“是括號不匹配的！ 現在你的任務是確定你有多少種填寫方案，使得最終的字符串是括號匹配的！2種方案是不同的，當2種方案中至少存在1個填寫字符是不同的。 例如，對於”((??))”,我們可以得到2種方案: “((()))”, “(()())”。

Input

數據包含多組測試數據第一行輸入一個字符串S(S的長度不超過16)。

Output

輸出一個整數,表示合法的填寫方案數。

Sample Input

((??))

Sample Output

2


思路：
代碼：

#include
#include
using namespace std;

char s[20];
int len;
int ans;

void DFS(int i,int cnt)//cnt代表沒配對的（的個數
{
    if(i==len&&cnt==0)
    {
        ans++;
    }
    if(cnt<0||i>=len)
        return;
    if(s[i]=='(')
        DFS(i+1,cnt+1);
    else if(s[i]==')')
        DFS(i+1,cnt-1);
    else
    {
        DFS(i+1,cnt+1);
        DFS(i+1,cnt-1);
    }
}

int main()
{
    while(scanf("%s",s)==1)
    {
        len=strlen(s);
        ans=0;
        DFS(0,0);
        printf("%d\n",ans);
    }
    return 0;
}