放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

UVa Q101: The Blocks Problem

Q101: The Blocks Problem

在早期人工智慧的领域中常常会用到机器人,在这个问题中有一支机器手臂接受指令来搬动积木,而你的任务就是输出最后积木的情形。

一开始在一平坦的桌面上有n块积木(编号从0到n-1)0号积木放在0号位置上,1号积木放在1号位置上,依此类推,如下图。

机器手臂有以下几种合法搬积木的方式(a和b是积木的编号):

  • move a onto b
    在将a搬到b上之前,先将a和b上的积木放回原来的位置(例如:1就放回1的最开始位罝)

  • move a over b
    在将a搬到b所在的那堆积木之上之前,先将a上的积木放回原来的位罝(b所在的那堆积木不动)

  • pile a onto b
    将a本身和其上的积木一起放到b上,在搬之前b上方的积木放回原位

  • pile a over b
    将a本身和其上的积木一起搬到到b所在的那堆积木之上

  • quit
    动作结束

前四个动作中若a=b,或者a, b在同一堆积木中,那么这样的动作算是不合法的。所有不合法的动作应该被忽略,也就是对各积木均无改变。

Input

输入含有多组测试资料,每组测试资料的第一列有一个正整数n(0 < n < 25),代表积木的数目(编号从0到n-1)。接下来为机器手臂的动作,每个动作一列。如果此动作为 quit ,代表此组测试资料输入结束。你可以假设所有的动作都符合上述的样式。请参考Sample Input。

Output

每组测试资料输出桌面上各位置积木的情形(每个位置一列,也就是共有n列),格式请参考Sample Output。

Sample 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
4
pile 0 over 1
pile 2 over 3
move 1 onto 3
quit

Sample Output

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

简体中文由Lucky貓的 UVA(ACM)園地转换。

原题链接http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=3&problem=37&mosmsg=Submission+received+with+ID+12862456

没什么难的,纯粹if else,无非过程复杂。

需要注意:

①这题数据结构千万不要用deque,TLE。换list过了。我也不知道我怎么糊涂地用了双头队列。

//#pragma warning(disable : 4996)
#include <iostream>
#include <string>
#include <algorithm>
#include <list>
using namespace std;

#define MAX 25
int n = 0;
list<int> block[MAX];
typedef list<int>::iterator dit;

void print_blocks()
{
	for (int i = 0; i < n; ++i)
	{
		cout << i << ':';
		for (dit it = block[i].begin(); it != block[i].end(); ++it)
		{
			cout << ' ' << *it;
		}
		cout << endl;
	}
}

list<int>::iterator search(int& index, const int& x)
{
	for (index = 0; index < n; ++index)
	{
		list<int>::iterator it = find(block[index].begin(), block[index].end(), x);
		if (it != block[index].end())
		{
			return it;
		}
	}
}

void restore(const int& index, dit itx)
{
	++itx;
	while (itx != block[index].end())
	{
		block[*itx].push_back(*itx);
		itx = block[index].erase(itx);
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	// 	freopen("in.txt", "r", stdin);
	// 	freopen("out.txt", "w", stdout);
	cin >> n;

	for (int i = 0; i < n; ++i)
	{
		block[i].clear();
		block[i].push_back(i);
	}

	string cmd;
	while (cin >> cmd)
	{
		if (cmd == "quit")
		{
			print_blocks();
			break;
		}
		else
		{
			string param;
			int a, b;
			cin >> a >> param >> b;
			if (a == b)
			{
				continue;
			}
			int na;
			dit pa = search(na, a);
			int nb;
			dit pb = search(nb, b);
			if (na == nb)
			{
				continue;
			}
			if (cmd == "move")
			{
				if (param == "onto")
				{
					restore(na, pa);
					restore(nb, pb);
					block[nb].push_back(*pa);
					block[na].erase(pa);
				}
				else if (param == "over")
				{
					restore(na, pa);
					block[nb].push_back(*pa);
					block[na].erase(pa);
				}
			}
			else if (cmd == "pile")
			{
				if (param == "onto")
				{
					restore(nb, pb);
					while (pa != block[na].end())
					{
						block[nb].push_back(*pa);
						pa = block[na].erase(pa);
					}
				}
				else if (param == "over")
				{
					while (pa != block[na].end())
					{
						block[nb].push_back(*pa);
						pa = block[na].erase(pa);
					}
				}
			}
		}
	}
	/*system("out.txt");*/
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » UVa Q101: The Blocks Problem

分享到:更多 ()

评论 欢迎留言

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机