[ Uva 101 详解 ] the block problem 木块问题

题目

输入 n
编号 0 ~ n-1 的木块,分别摆放在顺序排列编号为 0 ~ n-1 的位置。,要求模拟以下 4 种操作(下面的 a 和 b 都是木块编号)

  • move a onto b:把 a 和 b 上方的木块全部归位,然后把 a 摞在 b 上面
  • move a over b:把 a 上方的木块全部归位,然后把 a 放在 b 所在木块堆的顶部
  • pile a onto b:把 b 上方的木块全部归位,然后把 a 及上面的木块整体摞在 b 上面
  • pile a over b:把 a 及上面的木块整体摞在 b 所在木块堆的顶部

遇到 quit 时终止一组数据。a 和 b 在同一堆的指令是非法指令,应当忽略。

Input

10
move 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6
pile 8 over 5
move 2 over 1
move 4 over 9
quit

Output

 0: 0
 1: 1 9 2 4
 2:
 3: 3
 4:
 5: 5 8 7 6
 6:
 7:
 8:
 9:

分析

数据存储:
n 表示有多少位置,观察输出结果后,可以用一个定长数组来存储位置,在那个位置上的方块数量会根据操作增加或减少,属于不定长,可以使用 vector 数组来存储

vector<int> pile[100]; // 用这条来创建一个 有100个位置,每个位置一个不定长数组的数组来储存

操作分析:
观察 4 个命令,大体上动作只有 归位 和 移动,可以定义为两个函数,方便复用

接着 4 个命令放一起对比,4 个命令都有 移动 的动作,这意味着我们只需要判断何时进行 归位 的动作即可

前两个命令进行对比后,似乎带有 move 的都会让 a 归位,有 onto 的会把 b 归位

后两个命令也是如此,如果既没有 move 又没有 onto,则只进行 移动 动作

操作实现:
首先是归位,即把 a 以上的木块放回与其编号对应的位置,那么我们需要知道当前 a 所在的位置和处在这个位置中的什么地方,
假定用 p 来表示位置,h 来表示高度,
默认时,编号为 1 的块就在 p = 1, h = 0 的位置,
移动到编号为 2 块上面时,位置变为 p = 2, h = 1 (注意每个位置默认是有一个块的)
那么如何表示位置便清晰了,
接着是如何找到位置,很明显这个操作是会经常复用的,我们来定义一个 find 函数来实现这个功能

void find_block(int a, int& p, int& h)                // a 是查找的木块编号 ,p 和 h 采用引值传导,这样就能修改主函数中位置
{
	for ( p = 0; p < n; p++)                      // 从一切的起点开始遍历,找到对应则直接退出
	{
		for ( h = 0; h < pile[p].size(); h++) // vector容器的 .size() 方法可以返回不定长数组此时的长度,避免越界
		{
			if (a == pile[p][h]) return;
		}
	}
}

那么现在我们已经可以得到任意一个编号木块的位置了,接着实现把上面的木块一个个归位的动作

void goback(int p, int h)
{       int num = 0;
	for (int i = h+1; i < pile[p].size(); i++) // 从当前高度+1处开始归位
	{      num = pile[p][i];                   // 临时储存,你也可以直接用 pile[p][i] 代替 mun,不过那样的话下一行就太过复杂
		pile[num].push_back(num);          // 使用 vector 的 .push_back() 方法,可以将一个值添加到对应不定长数组中的最后
	}
	pile[p].resize(h + 1);                    // .resize() 则是将数组重新限定长度,不够的补齐,多的直接舍弃,因为编号是从0开始,所以要想保存 当前号,需要 +1
}

归位写好之后,移动就很简单了

void move(int p1, int h1, int p2)
{
	for (int i = h1; i < pile[p1].size(); i++) // 这边之所以不对 i +1,因为移动的是 a及a以上
	{
		pile[p2].push_back(pile[p1][i]);  // 同理
	}
	pile[p1].resize(h1);                      // 当前值也删去
}

目前关键操作已经清晰了,接下来就是润色润色,添加一些细节

细节处理:
命令输入是字符串混合数字,使用getchar一个一个读实在麻烦,scanf又不太好实现
所以我们采用流输入,并且用字符串搭配使用,引入 iostream库 和 string库

cin >> s1 >> a >> s2 >> b; //可以直接处理掉

成品代码

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>


using namespace std;

const int MAXN = 100;
vector<int> pile[MAXN];
int n = 0;



void find_block(int a, int& p, int& h);
void goback(int p, int h);
void move(int p1, int h1, int p2);

int command();



int main()
{
	while (scanf_s("%d", &n) != EOF)
	{
		for (int i = 0; i < n; i++)
		{
			pile[i].clear();
			pile[i].push_back(i);
		}

		while (command());											// 开始处理


		for (int i = 0; i < n; i++)									// 输出结果
		{
			printf("%d :", i);
			for (int j = 0; j < pile[i].size(); j++)
			{
				printf("  %d", pile[i][j]);
			}
			printf("\n");
		}


	}
}

int command()
{
	int a, b;
	string s1, s2;
	int n1 = 0;
	for (;;)
	{
		int p1, h1, p2, h2;
		cin >> s1 >> a >> s2 >> b;
		if (s1 == "quit") return 0;
		find_block(a, p1, h1);
		find_block(b, p2, h2);
		if (p1 == p2) continue;
		if (s2 == "onto") goback(p2, h2);
		if (s1 == "move") goback(p1, h1);
		move(p1, h1, p2);
	}
}

void find_block(int a, int& p, int& h)
{
	for ( p = 0; p < n; p++)
	{
		for ( h = 0; h < pile[p].size(); h++)
		{
			if (a == pile[p][h]) return;
		}
	}
}

void goback(int p, int h)
{
	for (int i = h+1; i < pile[p].size(); i++)
	{
		pile[i].push_back(i);
	}
	pile[p].resize(h);
}

void move(int p1, int h1, int p2)
{
	for (int i = h1; i < pile[p1].size(); i++)
	{
		pile[p2].push_back(pile[p1][i]);
	}
	pile[p1].resize(h1);
}

[ Uva 101 详解 ] the block problem 木块问题

上一篇:Markdown学习


下一篇:HADOOP MAPREDUCE(12):MapReduce开发总结