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 101 The Block Problem
	* Author: chchwy
	* Last Modified: 2011.06.16
	* Blog: http://chchwy.blogspot.com
	*/
	#include<cstdio>
	#include<cstring>
	#include<list>
	#include<algorithm>
	using namespace std;
	list<int> stk[25]; // the blocks
	int pos[25]; // current position of each block
	void init_block(int n)
	{
	for (int i = 0; i < n; ++i)
	{
	stk[i].clear();
	stk[i].push_back(i);
	}
	for (int i = 0; i < n; ++i)
	pos[i] = i;
	}
	bool in_the_same_stack(int x, int y)
	{
	return (pos[x] == pos[y]);
	}
	// clear all the blocks above 'x'
	void clear_above(int x)
	{
	int px = pos[x];
	while (stk[px].back() != x)
	{
	// place block 'num' to its original stack[num]
	int num = stk[px].back();
	stk[num].push_back(num);
	pos[num] = num;
	stk[px].pop_back();
	}
	}
	void move(int x, int y)
	{
	int px = pos[x], py = pos[y];
	auto move_begin = std::find(stk[px].begin(), stk[px].end(), x);
	auto move_end = stk[px].end();
	// append blocks (move_begin ~ move_end) to the end of stk[pos[y]]
	stk[py].insert(stk[py].end(), move_begin, move_end);
	//update pos array
	for (auto it = move_begin; it != move_end; ++it)
	{
	pos[ (*it) ] = py;
	}
	stk[px].erase(move_begin, move_end);
	}
	void print_result(int num_blocks)
	{
	for (int i = 0; i < num_blocks; ++i)
	{
	printf("%d:", i);
	for (int j = 0; j < stk[i].size(); ++j)
	printf(" %d", stk[i][j] );
	putchar('\n');
	}
	}
	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("101.in", "r", stdin);
	#endif
	int num_blocks;
	scanf("%d", &num_blocks);
	init_block(num_blocks);
	char cmd1[10], cmd2[10];
	int a, b;
	// [move/pile] a [onto/over] b
	while (scanf("%s %d %s %d", cmd1, &a, cmd2, &b) == 4)
	{
	// ignore illegal command
	if (a == b) continue;
	if (in_the_same_stack(a, b)) continue;
	if (strcmp("move", cmd1) == 0)
	clear_above(a);
	if (strcmp("onto", cmd2) == 0)
	clear_above(b);
	move(a, b);
	}
	print_result(num_blocks);
	return 0;
	}

view raw 101.cpp hosted with ❤ by GitHub