【UVA 101】 区块世界 The Blocks Problem or【POJ No.1208】

【UVA 101】 区块世界 The Blocks Problem or【POJ No.1208】

题目地址

【题意】

在早期的人工智能规划和机器人研究中使用了一个区块世界，在这个世界中，机器人手臂执行涉及区块操作的任务。问题是要解析一系列命令，这些命令指导机器人手臂如何操作平板上的块。最初，有n 个区块（编号为0～n −1），对于所有0≤i

用于操作块的有效命令有：

• move a onto b：把a和b上方的块全部放回初始位置，然后把a放到b上方。
• move a over b：把a上方的块全部放回初始位置，然后把a放到b所在块堆的最上方。
• pile a onto b：把b上方的块全部放回初始位置，然后把a和a上方所有的块整体放到b上方。
• pile a over b：把a和a上方所有的块整体放到b所在块堆的最上方。
• quit：结束标志。

任何a=b或a和b在同一块堆中的命令都是非法命令。所有非法命令都应被忽略。

【输入输出】

输入：

输入的第1行为整数n （0

输出：

输出应该包含区块世界的最终状态。每一个区块i （0≤i

【样例】

【思路分析】

初始时，从左到右有 n 个区块，(0 < n < 25)，编号为0 ~ n - 1，对其实现一些操作。

• move：将 a 上方的块全部放回初始位置
• onto：将 b 上方的块全部放回初始位置。
• 公共操作：将 a 和 a 上方所有的块 整体 放到 b 所在块堆的最上方。

实际上，前两种可以算做一个操作：即将 a (或b) 上方的块全部放回初始位置，简称归位。将a 和 a 上面的所有块整体放到 b 所在块堆的最上方 ， 简称移动。

【算法设计】

1. 读取操作命令 s1，如果s1 = “quit”，则结束；否则执行下两步
2. 读入操作命令 a s2 b，如果 s2 = “move”，则a 归位；如果 s2 = “onto”，则b 归位。
3. 执行移动操作，即将a 和 a上方所有的块整体放到 b 所在块堆 的最上方。

[如何执行归位 和 移动操作]

【归位】

要想使a上方的所有块归位，则首先要找到a所在的块堆，并知道a在块堆中的位置（高度），然后才能将a上方的所有块归位。

举个栗子：

块堆如下图所示，将8上方所有的块归位。首先查找到8所在的块堆为1，8所在块堆的高度为2，然后将1号块堆高度大于2的所有块放回原来的位置。

算法实现：

void goback(int p , int h){ //将p块堆高度大于h的所有块归位
	for(int i = h + 1 ; i < block[p].size() ; i++){
		int k = block[p][i];
		block[k].push_back(k);
	}
	block[p].resize(h + 1); //重置大小
}
1
2
3
4
5
6
7

【移动】

要想将a和a上方所有的块整体放到b所在块堆的最上方，则首先要找到a和b所在的块堆，如果a、b所在的块堆一样，则什么都不做。否则，将a块堆中高度大于或等于h （a的高度）的所有块移动到b所在块堆的上方。

例如，块堆如下图所示，将8和8上方所有的块整体放到9所在块堆的最上方。首先查找到8所在的块堆为5号，9所在的块堆为1号，8所在块堆的高度为1，然后将5号块堆高度大于或等于1的所有块放到1号块堆的上方，如下图所示。

算法实现：

void moveall(int p , int h , int q){ // 将p块堆高度大于或等于h的所有块都移动到q块堆的上方
	for(int i = h; i < block[p].size() ; i++){
		int k = block[p][i];
		block[q].push_back(k);
	}
	block[p].resize(h); //重置大小
}
1
2
3
4
5
6
7

【完美图解】

以样例为例：

初始有10个区块，开始时每个块都在对应的位置

move 9 onto 1：意思是将9 和 1 上方的块全部放回初始位置，然后把 9 放到1的上方。

move 8 over 1：将 8 上方的块全部放回初始位置，然后把8放到1的上方。

move 7 over 1：将 7 上方的块全部放回初始位置，然后把 7 放到 1 的上方。
move 6 over 1：将 6 上方的块全部放回初始位置，然后把 6 放到 1 的上方。

pile 8 over 6：将 8 和 8 上方所有的块整体放到 6 所在块堆的最上方，因为此时 8 和 6 在同一块堆中，所以什么也不做。

pile 8 over 5：将 8 和 8 上方所有的块整体放到 5 所在块堆的最上方，即将 8 、 7 、6 全部一起放到 5 所在块堆的上方。

move 2 over 1：将 2 上方的块全部放回初始位置，将 2 放到1所在块堆的最上方。

move 4 over 9：将 4 上方的块全部放回初始位置，将 4 放到 9 所在块堆的最上方。

quit：结束。

最后：从左到右、从下到上输出每个位置的块编号。

【算法实现】

因为每一个块堆的长度都发生了变化，因此可以使用变长数组vector，即对每个块堆都用一个vector存储。块堆的个数为n （0

#include
#include
#include
#include
#include

using namespace std;

vector<int>block[30];
int n;

void init(){
	
	cin >> n;
	for(int i = 0 ; i < n ; i++){
		
		block[i].push_back(i);
		
	}
	
}

void loc(int x , int &p , int &h){ //找位置 
	
	for(int i = 0 ; i < n ;i ++){
		
		for(int j = 0 ; j < block[i].size() ; j ++){
			
			if(block[i][j] == x){
				
				p = i;
				h = j;
				
			}
			
		}
		
	}
}

void goback(int p , int h){ //p堆 > h 的所有块归位 
	
	for(int i = h + 1; i < block[p].size() ; i++){
		
		int k = block[p][i];
		block[k].push_back(k);
		
	}
	block[p].resize(h + 1); //重置大小 
}

void moveall(int p , int h , int q){ //p堆 >= h 的所有块移动到q 之上 
	
	for(int i = h ; i < block[p].size() ; i ++){
		
		int k = block[p][i];
		block[q].push_back(k);
		
	}
	block[p].resize(h); //重置大小 
}

void solve(){
	
	int a, b;
	string s1 , s2;
	
	while(cin >> s1){
		
		if(s1 == "quit"){
			
			break;
			
		}
		
		cin >> a >> s2 >> b;
		int ap = 0;
		int ah = 0;
		int bp = 0;
		int bh = 0;
		
		loc(a , ap , ah);
		loc(b , bp , bh);
		
		if(ap == bp){
			
			continue;
			
		}
		if(s1 == "move"){ //a归位 
			
			goback(ap , ah);
			
		}
		if(s2 == "onto"){ //b 归位 
			
			goback(bp , bh);
		}
		moveall(ap , ah , bp);
	}
}

void print(){
	
	for(int i = 0 ; i < n ; i ++){
		
		cout << i << ":";
		for(int j = 0 ; j < block[i].size() ; j ++){
			
			cout << " " << block[i][j];
			
		}
		
		cout << endl;	
	}
}

int main(){
	
	init();
	solve();
	print();
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125

POJ 里面的题目地址【UVA 太容易挂了】