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。


留言

這個網誌中的熱門文章

UVa 10125 Sumsets

讀書心得: 撒哈拉的故事

讀書心得: 你以為你以為的就是你以為的嗎?