UVa 101 The Blocks Problem

解題策略

模擬機器手臂推方塊，典型的模擬題，乖乖照著命令的意思操作方塊，然後細心一點吧。

這題雖然有四個命令 [move/pile] a [onto/over] b，但是仔細觀察，就發現命令只分成兩種，一種是搬動方塊之前，要把目標上面的方塊都歸位(move/onto)，另一種是整疊方塊直接跟著搬動(pile/over)。

以下的程式，move()是搬動方塊，clear_above()是歸位的動作。整個處理的主迴圈就長這樣:

// 指令格式 [move/pile] a [onto/over] b
    while( scanf("%s %d %s %d", cmd1, &a, cmd2, &b)==4 ) {

        // 排除不合理的命令
        if(a==b) continue;
        if( in_the_same_stack(a,b) ) continue;
 
        // [move a] 把a上頭的方塊都歸位，[pile a] 則什麼都不做。
        if( strcmp("move", cmd1)==0 ) 
            clear_above(a); 

        // [onto b] 把b上頭的方塊都歸位，[over b] 則什麼都不做。
        if( strcmp("onto", cmd2)==0 ) 
            clear_above(b);

        // 搬動方塊
        move(a,b);
    }

閒聊

把年以前寫的爛code重新整理了一番，把linked list換成vector，速度也小進: 0.030s -> 0.008s。

以下完整code。