はなたの日記

プログラミング(C言語)の勉強をしています。超初心者です。

ALDS1-ALDS1_3_D Areas on the Cross-Section Diagram

問題
模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judge

全く分からず放置していました。なんとなくスタックを使いそう、って思ってから一歩も進みませんでした。
こちらの方が丁寧に説明してくれています。
mtdtx9.hatenablog.com

インデックスから面積を求めるとか、横で求めて結合するとか、自分じゃ一生思いつけないなと思いました。
いつもの通りc言語にて実装です。
Stack1に「\のインデックス」、Stack2に「popされた\のインデックスと面積の組(構造体)」をpushします。

#include<stdio.h>
#include<string.h>
#define MAX 20001

typedef struct idx_S{
 int idx;
 int S;
}idx_S;


void push1(int S[],int x,int *top){
 S[*top]=x;
 (*top)++;
return;
}

void push2(idx_S S[],int idx,int s,int *top){
 S[*top].idx=idx;
 S[*top].S=s;
 (*top)++;
return;
}

int pop(int S[],int *top){
 (*top)--;
 return S[*top];
}

void Union(idx_S S[],int *top){
 int i;

 for(i=(*top)-1;i>0;i--){

   if(S[i].idx < S[i-1].idx){
     (*top)--;
     S[i-1].idx=S[i].idx;
     S[i-1].S+=S[i].S;
   }

 }

return;
}

int main(){
 int i,j;
 char str[MAX];
 int idx;
 int Stack1[MAX];
 idx_S Stack2[MAX];
 int top1=0;
 int top2=0;
 int sum=0;

 scanf("%s",str);

 for(i=0;i<strlen(str);i++){

  switch(str[i]){
   case '\\':push1(Stack1,i,&top1);
             break;
   case '/' :if(top1==0)break;
             idx=pop(Stack1,&top1);
             sum+=(i-idx);
             push2(Stack2,idx,i-idx,&top2);
             Union(Stack2,&top2);
             break;
  }

 }

 printf("%d\n",sum);
 if(top2 == 0)printf("%d\n",top2);
 else {
   printf("%d ",top2);
   for(i=0;i<top2-1;i++)printf("%d ",Stack2[i].S);
   printf("%d\n",Stack2[top2-1].S);
 }

return 0;
}

Stack1に何も入ってない状態で「/」が入力された時の動作を考えず、躓きました。ifで対応。
数学にしろプログラミングにしろ、自分じゃ絶対思いつけない解法を見ると、頭の良い人はすごいなぁ(小並感)ってなります。