Windless
订阅/Feed
稗田千秋(i@wind.moe)

hihoCoder 1291 - Building in Sandbox 题解

稗田千秋
Apr.10 2016 algorithm

描述

Little Hi is playing a sandbox voxel game. In the game the whole world is constructed by massive 1x1x1 cubes. The edges of cubes are parallel to the coordinate axes and the coordinates (x, y, z) of the center of each cube are integers.

At the beginning there is nothing but plane ground in the world. The ground consists of all the cubes of z=0. Little Hi needs to build everything by placing cubes one by one following the rules:

  1. The newly placed cube must be adjacent to the ground or a previously placed cube. Two cubes are adjacent if and only if they share a same face.

  2. The newly placed cube must be accessible from outside which means by moving in 6 directions(up, down, left, right, forward, backward) there is a path from a very far place - say (1000, 1000, 1000) in this problem - to this cube without passing through ground or other cubes.

Given a sequence of cubes Little Hi wants to know if he can build the world by placing the cubes in such order.

输入

The first line contains the number of test cases T(1 <= T <= 10).

For each test case the first line is N the number of cubes in the sequence.

The following N lines each contain three integers x, y and z indicating the coordinates of a cube.

For 20% of the data, 1 <= N <= 1000, 1 <= x, y, z <= 10.

For 100% of the data, 1 <= N <= 100000, 1 <= x, y, z <= 100.

输出

For each testcase output "Yes" or "No" indicating if Little Hi can place the cubes in such order.

样例输入

3
3
1 1 1
1 2 1
1 3 1
3
1 1 1
1 2 1
1 3 2
17
1 1 1
1 2 1
1 3 1
2 3 1
3 3 1
3 2 1
3 1 1
2 1 1
2 1 2
1 1 2
1 2 2
1 3 2
2 3 2
3 3 2
3 2 2
2 2 2
2 2 1

样例输出

Yes
No
No

解题思路

先简要翻译一下题意(巨硬不忘推广MC啧啧,可理解为在MC中你拥有一块超平坦地形,每个方块拥有 1×1×1 的体积,Z 坐标为0的地面上已经铺满了方块,现在我们要添加方块,有两个要求:

1.只能紧挨着一个已有的方块放置,当且仅当两个方块共享一个面时为两个方块紧邻 2.方块只能从一个无限远的地方寻路径放进去,不能穿过其他方块

最后给出这个建筑能否被修建出来。

一开始的思路是使用并查集,即将搭建好的建筑假想为一张无向图,不断归并来求解,写着写着思路全乱了...然后又在时间轴上看见了菊苣夏洋的题目分析 ,茅塞顿开,既然放置方块的解法过于复杂,那何不反之从拆的过程着手呢?于是可以开两个三维数组 Sandbox和 Freebox ,分别表示有放置方块的坐标以及没有放置方块的坐标,然后在建筑完成后任取一闲置方块进行 FloodFill 来将闲置方块标记,然后逆序来拆掉方块(用栈存储),每拆掉一个便再进行一次仅针对释放方块的 FloodFill,这步很重要,因为可能在建筑内部构成一个真空,若最后成功逆序拆掉了所有方块,便可返回正确结果,然后对细节进行一些处理便可便可得出效率较高的解法。

Source Code

#include <cstdio>
#include <cstring>
#include <stack>
#define LENGTH 100 + 2
#define FOR(x, y, z) for (x = y; x < z; x++)
#define FREE(x)                                                                
  while (!x.empty())                                                           
  x.pop()
#define MAX(x, y) x = x > y ? x : y
#define MEM(x) memset(x, 0, sizeof(x))

using namespace std;

int i, j, k, max_num[4], dir[6][3] = {{-1, 0, 0}, {0, -1, 0}, {0, 0, -1},
                                      {1, 0, 0},  {0, 1, 0},  {0, 0, 1}};
bool flag, sandbox[LENGTH][LENGTH][LENGTH], freebox[LENGTH][LENGTH][LENGTH];

struct Point {
  int x, y, z;
  Point() {}
  Point(int x, int y, int z) : x(x), y(y), z(z) {}
};
stack<Point> points, flood;

bool valid(int x, int y, int z) {
  if (sandbox[x][y][z])
    return false;
  FOR(i, 0, 6)
  if (z == 1 || sandbox[x + dir[i][0]][y + dir[i][1]][z + dir[i][2]])
    return true;
  return false;
}

bool valid_free(int x, int y, int z) {

  FOR(i, 0, 6)
  if (freebox[x + dir[i][0]][y + dir[i][1]][z + dir[i][2]])
    return true;

  return false;
}

void floodfill(int x, int y, int z) {
  Point p(x, y, z);
  flood.push(p);
  while (!flood.empty()) {
    int x = flood.top().x, y = flood.top().y, z = flood.top().z;
    flood.pop();
    if (x < 0 || x > 101 || y < 0 || y > 101 || z < 1 || z > 101)
      continue;
    if (sandbox[x][y][z] || freebox[x][y][z])
      continue;
    freebox[x][y][z] = true;
    FOR(i, 0, 6)
    flood.push(Point(x + dir[i][0], y + dir[i][1], z + dir[i][2]));
  }
}

void record(int x, int y, int z) {
  MAX(max_num[0], x);
  MAX(max_num[1], y);
  MAX(max_num[2], z);
}
void init() {
  flag = false;
  MEM(sandbox);
  MEM(freebox);
  FREE(points);
  FREE(flood);
  FOR(i, 0, 3)
  max_num[i] = -1;
  FOR(i, 0, LENGTH)
  FOR(j, 0, LENGTH)
  sandbox[i][j][0] = true;
}
void pruning() {
  FOR(i, max_num[0] + 2, LENGTH)
  FOR(j, 0, LENGTH)
  FOR(k, 1, LENGTH)
  sandbox[i][j][k] = true;
  FOR(i, 0, LENGTH)
  FOR(j, max_num[1] + 2, LENGTH)
  FOR(k, 1, LENGTH)
  sandbox[i][j][k] = true;
  FOR(i, 0, LENGTH)
  FOR(j, 0, LENGTH)
  FOR(k, max_num[2] + 2, LENGTH)
  sandbox[i][j][k] = true;
}

int main() {
  int t;
  scanf("%d", &t);
  while (t--) {
    int n;
    scanf("%d", &n);
    init();
    while (n--) {
      Point p;
      scanf("%d %d %d", &p.x, &p.y, &p.z);
      record(p.x, p.y, p.z);
      if (!valid(p.x, p.y, p.z) && !flag)
        flag = true;
      points.push(p);
      sandbox[p.x][p.y][p.z] = true;
    }
    if (flag) {
      puts("No");
      continue;
    }
    pruning();
    floodfill(0, 0, 1);
    while (!points.empty()) {
      int x = points.top().x, y = points.top().y, z = points.top().z;
      points.pop();
      if (valid_free(x, y, z)) {
        sandbox[x][y][z] = false;
        floodfill(x, y, z);
      } else {
        puts("No");
        flag = true;
        break;
      }
    }
    if (flag)
      continue;
    puts("Yes");
  }
  return 0;
}

/********************
Status: Accepted
Time : 865ms
Memory : 23MB
Language: C++
********************/

在第一次 FloodFill 的基础上我们可以进行一次限制避免无所谓的搜索,使用 maxnum 数组分别记录 x,y,z 的最大值,将这三个值以外的部分直接标记为闲置方块,即将多余部分切掉,在数据量较少的时候可以节约很大一部分资源,不加 minnum 的原因是猜测数据应该都会从小值开始,因而感觉提升效率不大(事实也证明如此。

--END--
文章创建于 2016-04-10 11:16:04,最后更新 2016-04-10 11:16:04
Comment
尝试加载Disqus评论, 失败则会使用基础模式.
    • play_arrow

    About this site

    version:1.02 Alpha
    博客主题: Lime
    联系方式: i@wind.moe
    写作语言: zh_CN & en_US
    博客遵循 CC BY-NC-SA 4.0许可进行创作

    此外,本博客会基于访客的Request Headers记录部分匿名数据用于统计(Logger的源码见Github),包含Referer, User-Agent & IP Address.个人绝不会主动将数据泄露给第三方