U1.【UVA】块问题-The Blocks Problem(补充了pair的使用)
目录
1.题目
2.分析
单词积累
题目意思理解
测试用例的过程图描述
3.代码
前置知识:STL库的模版类:pair<类型1, 类型2>
查找积木函数find代码
move、pile、onto和over操作分析
归位函数clean代码
移动函数move代码
打印结果函数的代码
正确代码
完整代码
4.提交结果
5.其他说明
1.题目
题目描述
PDF版题目下载链接 点我跳转
输入格式
输出格式
题目翻译见:The Blocks Problem - 洛谷
由于UVA网站访问速度慢,因此可以去vjudege上提交The Blocks Problem - UVA 101 - Virtual Judge
2.分析
单词积累
manipulation 操纵
constraints 约束 限制
adjacent 相邻的
diagram 示意图
colon 冒号
题目意思理解
前面简单介绍了一下命题背景:使用机械臂操控木块打造"积木世界"
现要求编程来模拟打造的过程,只有4个有效指令,初始时输入积木的个数n(0<n<25),编号0~(n-1)在平面上一字排开
只有4个有效指令(需要理解介词onto和over的含义)
move a onto b 其中a和b是积木编号，将积木a放在积木b上。在执行此操作之前，需要将积木a和积木b上堆叠的所有积木放回其初始位置。
move a over b 其中a和b是积木编号，将积木a放在包含积木b的堆叠的顶部。在执行此操作之前，需要将积木a上堆叠的所有积木放回其初始位置。
pile a onto b 其中a和b是积木编号，将包含积木a及其上方所有积木的堆叠移动到积木b上。在执行此操作之前，需要将积木b上堆叠的所有积木放回其初始位置。积木a上方的积木在移动时保持其原有顺序。
pile a over b 其中a和b是积木编号，将包含积木a及其上方所有积木的堆叠放在包含积木b的堆叠的顶部。积木a上方的积木在移动时保持其原有顺序。
quit 终止积木世界的操作。 任何a=b或a和b在同一个积木堆叠中的指令都是非法指令。所有非法指令应被忽略，并且不应影响积木的配置。
测试用例的过程图描述
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 9 onto 1
move 8 over 1
move 7 over 1
move 6 over 1
pile 8 over 6,由于积木8和积木6在同一个积木堆上,因此为非法指令
pile 8 over 5
move 2 over 1
move 4 over 9
quit
3.代码
由过程图可知,应该用vector数组:vector<int> arr[25]
输入n后应该对vector数组初始化:即循环来尾插一个元素,可以写在类的构造函数里
注意:指令中的a和b指定不是下标,而是对应的积木编号,因此读完一条指令后应该先找到a和b位于哪个下标的积木堆上,这里可以写一个查找函数find,使其返回两个下标(位于?下标的积木堆上,位于积木堆的?位置),则查找函数find的返回值应该有两个下标,但之前函数的文章只讲过返回一个值的函数,这里要引入STL库的pair模版
前置知识:STL库的模版类:pair<类型1, 类型2>
头文件:<utility>
pair可以简单理解为C++里面的结构体,里面两个变量
struct pair
{
type first;
type second;
}first和second可以定义为自己想要的任意类型
例如:pair<int, int>表示pair对象包含两个int类型的值,使用p.first和p.second来分别访问pair的第一个和第二个元素
#include <iostream>
#include <utility>
using namespace std;
int main() {
pair<int, int> p = {1, 2};
cout << "First: " << p.first << " Second: " << p.second;
return 0;
}由于pair<?,?>x写起来较麻烦,因此可以typedef
typedef pair<int,int> PII;//PII:P为pair,I为int
PII a;
typedef pair<long,int> PLI;//PII:P为pair,L为long
PLI b;
typedef pair<long,long> PLL;
PLL c;查找积木函数find代码
pair<int,int> find(int data)
{
for (int i=0;i<n;i++)
{
for (int j=0;j<arr[i].size();j++)
{
if (arr[i][j]==data)//如果找到
{
return {i,j};//注意写法{?,?}
}
}
}
}注意pair<类型1,类型2>返回值的写法:return {?,?};
move、pile、onto和over操作分析
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 的上面。
拆解步骤:
move: a上方归位
pile: a及a以上的积木放在b上
onto: b上方归位,a及a以上的积木放在b上
over:a及a以上的积木放在b上
例如move a onto b:a上方归位+b上方归位,a及a以上(其实只有a)的积木放在b上
统一看来:只有两种操作:1.归位 2.a及a放在b上(移动)
归位函数clean代码
分析:
void clean(int x_a, int y_a)
{
for (int i = y_a + 1; i < arr[x_a].size(); i++)
{
arr[arr[x_a][i]].push_back(arr[x_a][i]);
}
arr[x_a].resize(y_a + 1);
}移动函数move代码
分析:
void move(int x_a, int y_a, int x_b)
{
for (int i = y_a; i < arr[x_a].size(); i++)
{
arr[x_b].push_back(arr[x_a][i]);
}
arr[x_a].resize(y_a);
}打印结果函数的代码
下面这个代码是错误的,一定要严格遵守题目的要求!!
void print()
{
for (int i=0;i<n;i++)
{
cout<<i<<": ";
for (int j=0;j<arr[i].size();j++)
{
cout<<arr[i][j]<<" ";
}
cout<<endl;
}
}
cout<<arr[i][j]<<" ";会导致尾部打印多余的空格,会判错!!!
正确代码
void print()
{
for (int i = 0; i < n; i++)
{
cout << i << ":";
for (int j = 0; j < arr[i].size(); j++)
{
cout << " " <<arr[i][j];//空格前置打印
}
cout << endl;
}
}完整代码
#include <iostream>
#include <utility>//pair模版
#include <vector>
#define endl "\n"//提高换行的运行速度
#pragma GCC optimize(3)//STL开O3优化
using namespace std;
class Solution
{
public:
int n;
vector<int> arr[25];
Solution(int num)//传参版的构造函数
{
for (int i = 0; i < num; i++)
{
arr[i].push_back(i);
}
n = num;
}
pair<int, int> find(int data)
{
for (int i = 0; i < n; i++)
{
for (int j = 0; j < arr[i].size(); j++)
{
if (arr[i][j] == data)//如果找到
{
return { i,j };//注意写法{?,?}
}
}
}
}
void print()
{
for (int i = 0; i < n; i++)
{
cout << i << ":";
for (int j = 0; j < arr[i].size(); j++)
{
cout << " " <<arr[i][j];
}
cout << endl;
}
}
void clean(int x_a, int y_a)
{
for (int i = y_a + 1; i < arr[x_a].size(); i++)
{
arr[arr[x_a][i]].push_back(arr[x_a][i]);
}
arr[x_a].resize(y_a + 1);
}
void move(int x_a, int y_a, int x_b)
{
for (int i = y_a; i < arr[x_a].size(); i++)
{
arr[x_b].push_back(arr[x_a][i]);
}
arr[x_a].resize(y_a);
}
};
int main()
{
//提高cin和cout的执行速度
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int n, a, b;
string op1, op2;
cin >> n;
Solution sol(n);//将参数n传给构造函数,用于初始化
while (1)
{
cin >> op1;
if (op1 == "quit")
break;
cin >> a >> op2 >> b;
pair<int, int> pair_a = sol.find(a);
int x_a = pair_a.first;//a的横坐标
int y_a = pair_a.second;//a的纵坐标
pair<int, int> pair_b = sol.find(b);
int x_b = pair_b.first;//a的横坐标
int y_b = pair_b.second;//a的纵坐标
if (x_a==x_b)
continue;
if (op1 == "move")
{
sol.clean(x_a, y_a);
}
if (op2 == "onto")
{
sol.clean(x_b, y_b);
}
sol.move(x_a, y_a, x_b);
}
sol.print();
return 0;
}4.提交结果
5.其他说明
有兴趣的读者可以去看看刘老师在《算法竞赛入门经典(第2版)》书中的第109页~第112页写的解法