#UVa:101-The Blocks Problem

這題就照著題目要求的模擬去做即可得解。

我用了一個叫做block的二維陣列去做模擬,其中又用了top的陣列去紀錄每一堆最上層是第幾格,然後還用了position去紀錄每一個格子目前在block當中的位置,這樣很容易就可以得解了!

步驟可以分成:

  1. 看看a上面是否要放回去。
  2. 看看b上面是否要放回去。
  3. a那堆(可能一個,可能很多個)把它放到b那堆。

這樣就算蠻簡化程式碼了XD

P.S. 要記得忽略a和b都放在同一堆的狀況喔!

C++(0.008)

/*******************************************************/
/* UVa 101 The Blocks Problem                          */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2012/03/16                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int main(){
  int position[30][2];
  int block[30][30];
  int top[30];
  int n;
  char action1[10], action2[10];
  int a, b, ax, ay, bx, by;

  while( scanf( "%d", &n ) != EOF ){
    for( int i = 0 ; i < n ; i++ ){
      position[i][0] = i;
      position[i][1] = 0;
      block[i][0] = i;
      top[i] = 1;
    }
    while( scanf( "%s", action1 ) != EOF && strcmp( action1, "quit" ) ){
      scanf( "%d%s%d", &a, action2, &b );

      ax = position[a][0];
      ay = position[a][1];
      bx = position[b][0];
      by = position[b][1];

      if( ax == bx ) continue;

      if( !strcmp(action1, "move") ){
        for( int i = ay+1 ; i < top[ax] ; i++ ){
          position[block[ax][i]][0] = block[ax][i];
          position[block[ax][i]][1] = top[block[ax][i]];
          block[block[ax][i]][top[block[ax][i]]++] = block[ax][i];
        }
        top[ax] = ay+1;
      }
      if( !strcmp(action2, "onto") ){
        for( int i = by+1 ; i < top[bx] ; i++ ){
          position[block[bx][i]][0] = block[bx][i];
          position[block[bx][i]][1] = top[block[bx][i]];
          block[block[bx][i]][top[block[bx][i]]++] = block[bx][i];
        }
        top[bx] = by+1;
      }

      for( int i = ay ; i < top[ax] ; i++ ){
        position[block[ax][i]][0] = bx;
        position[block[ax][i]][1] = top[bx];
        block[bx][top[bx]++] = block[ax][i];
      }
      top[ax] = ay;
    }

    for( int i = 0 ; i < n ; i++ ){
      printf( "%d:", i );
      for( int j = 0 ; j < top[i] ; j++ )
        printf( " %d", block[i][j] );
      printf( "\n" );
    }
  }

  return 0;
}

迴響 (2)

  1. eddie
    2015-10-25 @ 23:15:04

    我是CB260學生,用struct寫了UVA的The blocks program, 第一次能正確執行,但是第2次無論quit或繼續下指令, 都卡死在while的無窮迴圈裡, 請老師幫我看一下錯在哪, 謝謝大家

    題目網址: http://luckycat.kshs.kh.edu.tw

    我的code: http://pastebin.com/DC1T8ZGn

    回覆
    • 2015-11-30 @ 12:38:51

      依照上面的code看來,他並不會重複輸入第一次的指令,
      while裡面並沒有重新輸入action1的部分喔!

      回覆

發表迴響