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。
留言
張貼留言