?

/* sample input 3 walpurgis(charlotte(patricia,gertrud),elly,gisela) wuzetian nanoha(fate(hayate)) */ /* DFS 把樹的字符串 1 a(b(c,d),e,f) 進行深度優先搜索 當前房間編號i 遇到'('則i-》i+1 遇到','則i-》pre_i pre_i-》i+1 遇到')'則i-》pre_i 如果pre_i!=1 pre_i-》pre_i' pre_i'-》pre_i+1*/ #include <stdio.h> #include <string.h>int T;//T<=20 char str[1000002];//Madoka's log <=1000000chars char Witches[50001][11];//at most 50000 rooms int sum_witches,str_i,str_len,name_i,cur_i;//當前結點編號 int pre_i[50001];//父結點編號 int pass[100002][2];//路線 int pass_i; int main() {char ch;int t,i;scanf("%d",&T);while (T--){memset(pass,0,sizeof(pass)); pass_i=0;memset(Witches,0,sizeof(Witches));sum_witches=1;name_i=0;memset(pre_i,0,sizeof(pre_i));cur_i=1;pre_i[cur_i]=-1;memset(str,0,sizeof(str)); str_i=0;scanf("%s",str);str_len=strlen(str); while (str_i<str_len){ch=str[str_i++];switch(ch){case '(':sum_witches++;name_i=0;pre_i[sum_witches]=cur_i;pass[pass_i][0]=cur_i;pass[pass_i][1]=sum_witches;pass_i++;cur_i=sum_witches;break;case ',':t = pre_i[cur_i];pass[pass_i][0]=cur_i;pass[pass_i][1]=t;pass_i++;cur_i=t;sum_witches++;name_i=0;pre_i[sum_witches]=cur_i;pass[pass_i][0]=cur_i;pass[pass_i][1]=sum_witches;pass_i++;cur_i=sum_witches;break;case ')':t=pre_i[cur_i];pass[pass_i][0]=cur_i;pass[pass_i][1]=t;pass_i++;cur_i=t;break;default:Witches[sum_witches][name_i++]=ch;if(str[str_i]>'z' || str[str_i]<'a')Witches[sum_witches][name_i]='\0';break;}}printf("%d\n",sum_witches);for (i=1;i<sum_witches+1;i++) printf("%s\n",Witches[i]);for (i=0;i<pass_i;i++) printf("%d %d\n",pass[i][0],pass[i][1]);printf("\n");}return 1; }

?

轉載于:https://www.cnblogs.com/CheeseZH/archive/2012/04/11/2442144.html

總結

以上是生活随笔為你收集整理的Eliminate Witches!【2011年北京赛区正赛赛题-2】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。