Uva 101 - The Blocks Problem

[Submit]   [Go Back]   [Status]  

Description

Many areas of Computer Science use simple, abstract domains for both analytical and empirical studies. For example, an early AI study of planning and robotics (STRIPS) used a block world in which a robot arm performed tasks involving the manipulation of blocks. 
In this problem you will model a simple block world under certain rules and constraints. Rather than determine how to achieve a specified state, you will "program" a robotic arm to respond to a limited set of commands. 
The problem is to parse a series of commands that instruct a robot arm in how to manipulate blocks that lie on a flat table. Initially there are n blocks on the table (numbered from 0 to n-1) with block bi adjacent to block bi+1 for all 0 <= i < n-1 as shown in the diagram below: 

The valid commands for the robot arm that manipulates blocks are: 

move a onto b 
where a and b are block numbers, puts block a onto block b after returning any blocks that are stacked on top of blocks a and b to their initial positions. 


move a over b 
where a and b are block numbers, puts block a onto the top of the stack containing block b, after returning any blocks that are stacked on top of block a to their initial positions. 


pile a onto b 
where a and b are block numbers, moves the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto block b. All blocks on top of block b are moved to their initial positions prior to the pile taking place. The blocks stacked above block a retain their order when moved. 


pile a over b 
where a and b are block numbers, puts the pile of blocks consisting of block a, and any blocks that are stacked above block a, onto the top of the stack containing block b. The blocks stacked above block a retain their original order when moved. 


quit 
terminates manipulations in the block world. 

Any command in which a = b or in which a and b are in the same stack of blocks is an illegal command. All illegal commands should be ignored and should have no affect on the configuration of blocks. 

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

题目大意：

输入一系列指令让你移到木块
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

结束

解析：

这题最大的难点就是比较繁琐，但是耐心写还是能完成的。

原来想用字符串来模拟，但是不知道为什么一直RE

后来改用结构体模拟就AC了。

另外附上一组测试样例：

输入：

21
move 2 onto 1
move 3 onto 2
move 4 onto 3
move 5 over 1
pile 1 over 10
move 9 over 8
move 11 over 8
pile 3 over 8
pile 8 over 3
move 20 over 19
pile 19 over 18
pile 18 onto 15
move 15 over 3
pile 20 onto 19
pile 19 onto 18
pile 18 over 17
quit

输出：

0: 0
1:
2:
3:
4:
5:
6: 6
7: 7
8: 8 9 11 3 4 5 15
9:
10: 10 1 2
11:
12: 12
13: 13
14: 14
15:
16: 16
17: 17 18 19 20
18:
19:
20:

AC代码：

#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
const int N = 30;
struct Stack {
	int top;
	int num[N];
};
struct Block {
	int row;
	int col;
};
Stack stack[N];
Block block[N];
//初始化
void init(int n) {
	for(int i = 0 ;i < n; i++) {
		stack[i].top = 1;
		stack[i].num[0] = i;
		block[i].row = i;
		block[i].col = 0;
	}
}

void back(int a) {
	int x = block[a].row;
	int y = block[a].col;
	int top = stack[x].top;
	for(int i = top -1 ; i > y; i--) { //将a上面的所有元素都归位
		int topnum = stack[x].num[i]; //栈顶的数字
		stack[topnum].num[stack[topnum].top] = topnum;
		block[topnum].row = topnum;
		block[topnum].col = stack[topnum].top;
		stack[topnum].top++;
		stack[x].top--;
	}
}

void move(int a,int b) {
	int x_a = block[a].row;
	int y_a = block[a].col;
	int x_b = block[b].row;
	int y_b = block[b].col;
	stack[x_b].num[stack[x_b].top] = a;
	block[a].row = x_b;
	block[a].col = stack[x_b].top;
	stack[x_b].top++;
	stack[x_a].top--;
}

void pile(int a,int b) {
	int x_a = block[a].row;
	int y_a = block[a].col;
	int x_b = block[b].row;
	int y_b = block[b].col;
	int top = stack[x_a].top;
	for(int i = y_a; i < top; i++) {
		stack[x_b].num[stack[x_b].top] = stack[x_a].num[i];
		block[stack[x_a].num[i]].row = x_b;
		block[stack[x_a].num[i]].col = stack[x_b].top;
		stack[x_b].top++;
		stack[x_a].top--;
	}
}
int main() {
	int n;
	while(scanf("%d",&n) != EOF) {
		getchar();
		init(n);
		char str1[10],str2[10];
		int a,b;
		while(scanf("%s",str1)) {
			if(!strcmp(str1,"quit")) {
				break;
			}
			scanf("%d%s%d",&a,str2,&b);
			if(block[a].row == block[b].row) {
				continue;
			}
			if(!strcmp(str1,"move")) {
				if(!strcmp(str2,"onto")) {
					back(a);
					back(b);
					move(a,b);
				}
				else {
					back(a);
					move(a,b);
				}
			}
			else {
				if(!strcmp(str2,"onto")) {
					back(b);
					pile(a,b);
				}
				else {
					pile(a,b);
				}
			}
		}
		for(int i = 0; i < n; i++) {
			printf("%d:",i);
			for(int j = 0; j < stack[i].top; j++) {
				printf(" %d",stack[i].num[j]);
			}
			printf("n");
		}
	}
	return 0;
}

最后

以上就是悲凉树叶为你收集整理的Uva 101 - The Blocks Problem的全部内容，希望文章能够帮你解决Uva 101 - The Blocks Problem所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。