问题描述
p101原题链接：UVaOJ 101 The Blocks Problem
相关说明：本题为《算法竞赛入门经典（第2版）》例题 5-2
解法一：模拟
使用二维 vector 进行存储，并模拟执行 block 的移动，找到四种移动操作的共同点。对于原始块 source 和目标块 target, 都可能存在 clear_above 操作，即将各自上方的块回归到初始位置；剩下的操作是 move_above 操作，将 source 块和它上方的块直接叠加到 target 块所在的位置上方。容易出问题的点：如果不做两个 block 所在位置 pos 相同时的特判，容易导致 TLE （比如下面代码中注释掉的这一行，是我当时疏忽，将比较对象写错了，很难 DeBug 发现）。
|
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 |
#include <bits/stdc++.h> using namespace std; const int MAX_NUM = 30; vector<int> table[MAX_NUM]; int num; // less than MAX_NUM void find_block(int val, int& pos, int& height) { for (pos = 0; pos < num; ++pos) for (height = 0; height < table[pos].size(); ++height) if (table[pos][height] == val) return; } void clear_above(int pos, int height) { for (int i = height + 1; i < table[pos].size(); ++i) table[table[pos][i]].push_back(table[pos][i]); table[pos].resize(height + 1); } void move_above(int p_src, int h_src, int p_tar) { for (int i = h_src; i < table[p_src].size(); ++i) table[p_tar].push_back(table[p_src][i]); table[p_src].resize(h_src); } int main() { cin >> num; for (int i = 0; i < num; ++i) table[i].push_back(i); int source, target; string op1, op2; while (cin >> op1 >> source >> op2 >> target) { int p_src, p_tar, h_src, h_tar; find_block(source, p_src, h_src); find_block(target, p_tar, h_tar); // if (source == target) continue; if (p_src == p_tar) continue; if (op1 == "move") clear_above(p_src, h_src); if (op2 == "onto") clear_above(p_tar, h_tar); move_above(p_src, h_src, p_tar); } for (int i = 0; i < num; ++i) { cout << i << ":"; for (auto block : table[i]) cout << " " << block; cout << endl; } return 0; } |
|
1 |
#TODO |
