Ring's ACM

求一堆積木依照指令堆疊之後，最後的排列情形

[心得]

1. map[][] 儲存各個位置的積木編號，沒有積木的位置用-1表示

2. loc[] 儲存該編號的積木所在之行、end[] 表示該行最後一個積木的高度 (沒有為-1)

3.放回寫成函式back()，需要再呼叫即可，全域變數記得擺在最前面

4.每個動作都要考慮到 map、loc、end，改變的次序很重要，以及先用其他變數記錄

5. continue 的作用是回到迴圈起始點重新開始，可以用在不做任何改變的情況

#include <stdio.h>
#include <string.h>

    int n,i,j,k,a,b,map[25][25]; /* the blocks' number in map */
    int loc[25],end[25]; /* the height of loc[a] */

void back(int a)
{
     int h,t;
    
     for(h=end[loc[a]];map[loc[a]][h]!=a;h--)
     {
         map[map[loc[a]][h]][end[map[loc[a]][h]]+1]=map[loc[a]][h]; /* the number */
         loc[map[loc[a]][h]]=map[loc[a]][h]; /* the location */
         end[map[loc[a]][h]]++; /* the height */
         map[loc[a]][h]=-1;
         end[loc[a]]--;
     }
}

void pile_over(int a,int b)
{   
     int h,last,t1,t2,t3; /* the amount of blocks under a */
    
     for(h=0;h<n;h++)
         if(map[loc[a]][h]==a) /* get the height of a */
             break;
     last=end[loc[a]]-h;
     t1=end[loc[a]];
     t2=end[loc[b]];
     t3=loc[a];
     end[loc[a]]=end[loc[a]]-(last+1);
     end[loc[b]]=end[loc[b]]+(last+1);
    
     for(i=0,j=1;i<=last;i++,j++)
     {
         map[loc[b]][t2+j]=map[t3][h+i];
         loc[map[t3][h+i]]=loc[b];
         map[t3][h+i]=-1;
     }
}

void move_onto(int a,int b)
{
     back(a); back(b);
     pile_over(a,b);
}
void move_over(int a,int b)
{
     back(a);
     pile_over(a,b);
}
void pile_onto(int a,int b)
{
     back(b);
     pile_over(a,b);
}

int main()
{
    char str1[5],str2[5];
   
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
        {
            for(j=1;j<n;j++)
                map[i][j]=-1;
            map[i][0]=i;
            loc[i]=i;
            end[i]=0;
        }
       
        while(scanf("%s",str1))
        {
            if(!strcmp(str1,"quit"))
                break;
            scanf("%d %s %d",&a,str2,&b);
            if((a==b)||(loc[a]==loc[b]))
                continue; /* back to the start of while */
           
            if(!strcmp(str1,"move"))
                if(!strcmp(str2,"onto"))
                    move_onto(a,b);
                else
                    move_over(a,b);
            else
                if(!strcmp(str2,"onto"))
                    pile_onto(a,b);
                else
                    pile_over(a,b);
        }
        for(i=0;i<n;i++)
        {
            printf("%d:",i);
            for(j=0;j<n;j++)
                if(map[i][j]!=-1)
                    printf(" %d",map[i][j]);
            printf("\n");
        }
    }   
   
    return 0;
}