2012-12-26 22:12:35Morris
[UVA][stack] 12582 - Wedding of Sultan
題目意思：給定一個圖的走訪方式(dfs)，問每個節點的 degree。
解法：
既然原本 dfs 是用 stack 去寫，那麼還原也是 stack 去模擬。
第一次遇到的字母 = push()
第二次遇到的字母 = pop(), 同時 top 是相連的符號。
#include <stdio.h>
#include <string.h>
int main() {
int t, cases = 0, i;
scanf("%d", &t);
while(t--) {
char s[105];
int ans[128] = {}, stk[128];
int stkIdx = -1;
scanf("%s", s);
for(i = 0; s[i]; i++) {
if(stkIdx < 0 || stk[stkIdx] != s[i]) {
stk[++stkIdx] = s[i];
ans[s[i]]++;
} else {
stkIdx--;
if(stkIdx >= 0)
ans[stk[stkIdx]]++;
}
}
ans[s[0]]--;
printf("Case %d\n", ++cases);
for(i = 'A'; i <= 'Z'; i++)
if(ans[i])
printf("%c = %d\n", i, ans[i]);
}
return 0;
}
解法：
既然原本 dfs 是用 stack 去寫，那麼還原也是 stack 去模擬。
第一次遇到的字母 = push()
第二次遇到的字母 = pop(), 同時 top 是相連的符號。
#include <stdio.h>
#include <string.h>
int main() {
int t, cases = 0, i;
scanf("%d", &t);
while(t--) {
char s[105];
int ans[128] = {}, stk[128];
int stkIdx = -1;
scanf("%s", s);
for(i = 0; s[i]; i++) {
if(stkIdx < 0 || stk[stkIdx] != s[i]) {
stk[++stkIdx] = s[i];
ans[s[i]]++;
} else {
stkIdx--;
if(stkIdx >= 0)
ans[stk[stkIdx]]++;
}
}
ans[s[0]]--;
printf("Case %d\n", ++cases);
for(i = 'A'; i <= 'Z'; i++)
if(ans[i])
printf("%c = %d\n", i, ans[i]);
}
return 0;
}