MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 101 - The Blocks Problem
AOAPC II

UVaOJ 101 - The Blocks Problem

Chai
2021-11-24 0:00:00在线评测阅读 429

问题描述

p101

原题链接:UVaOJ 101 The Blocks Problem

相关说明:本题为《算法竞赛入门经典(第2版)》例题 5-2

解法一:模拟

使用二维 vector 进行存储,并模拟执行 block 的移动,找到四种移动操作的共同点。对于原始块 source 和目标块 target, 都可能存在 clear_above 操作,即将各自上方的块回归到初始位置;剩下的操作是 move_above 操作,将 source 块和它上方的块直接叠加到 target 块所在的位置上方。容易出问题的点:如果不做两个 block 所在位置 pos 相同时的特判,容易导致 TLE (比如下面代码中注释掉的这一行,是我当时疏忽,将比较对象写错了,很难 DeBug 发现)。

C++
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;
}
Python
1
#TODO
AOAPC II UVaOJ
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz