UVaOJ 101 - The Blocks Problem

问题描述

解法一：模拟

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

#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;
}

#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;

}

#TODO

#TODO

AOAPC II UVaOJ