程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> fzu 2030 括號問題(DFS)

fzu 2030 括號問題(DFS)

編輯:C++入門知識

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;
}


  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved