【hihocoder1291 微软2016校园招聘4月在线笔试D】【逆序思维 并查集】Buiding in Sandbox 我的世界建方块合法性判定

本文主要是介绍【hihocoder1291 微软2016校园招聘4月在线笔试D】【逆序思维 并查集】Buiding in Sandbox 我的世界建方块合法性判定，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 105, M = 1e5+10, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
bool e[N][N][N];
int n;
const int dz[6] = { -1,0,0,0,0,1 };
const int dx[6] = { 0,-1,0,0,1,0 };
const int dy[6] = { 0,0,-1,1,0,0 };
struct A
{int x, y, z;
}a[M];const int G = N * N * N;
int f[G];
int find(int x)
{return x == f[x] ? x : f[x] = find(f[x]);
}
const int V1 = 102 * 102;
const int V2 = 102;
bool merge(int x1, int y1, int z1, int x2, int y2, int z2)
{int o1 = x1*V1 + y1*V2 + z1;int o2 = x2*V1 + y2*V2 + z2;o1 = find(o1);o2 = find(o2);if (o1 != o2){f[o2] = o1;return 1;}else return 0;
}
bool solve()
{MS(e, 0);bool flag = 1;for (int i = 1; i <= n; ++i){scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);if (!flag)continue;int x = a[i].x;int y = a[i].y;int z = a[i].z;if (e[x][y][z])flag = 0;e[x][y][z] = 1;if (z == 1)continue;int k; for (k = 0; k < 6; ++k){int xx = x + dx[k];int yy = y + dy[k];int zz = z + dz[k];if (e[xx][yy][zz])break;}if (k == 6)flag = 0;}if (!flag)return 0;for (int i = 0; i <= 101; ++i){for (int j = 0; j <= 101; ++j){for (int k = 1; k <= 101; ++k){int o = i*V2 + j*V1 + k;f[o] = o;}}}for (int i = 0; i <= 101; ++i){for (int j = 0; j <= 101; ++j){for (int k = 1; k <= 101; ++k) if(!e[i][j][k]){for (int d = 0; d < 6; ++d){int x = i + dx[d];int y = j + dy[d];int z = k + dz[d];if (x < 0 || x>101 || y < 0 || y>101 || z < 1 || z>101)continue;if (!e[x][y][z])merge(i, j, k, x, y, z);}}}}for (int i = n; i >= 1; --i){int x = a[i].x;int y = a[i].y;int z = a[i].z;e[x][y][z] = 0; for (int d = 0; d < 6; ++d){int xx = x + dx[d];int yy = y + dy[d];int zz = z + dz[d];if (xx < 0 || xx>101 || yy < 0 || yy>101 || zz < 1 || zz>101)continue;if (!e[xx][yy][zz])merge(x, y, z, xx, yy, zz);}if (merge(x, y, z, 101, 101, 101))return 0;}return 1;
}
int main()
{scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){scanf("%d", &n);puts(solve() ? "Yes" : "No");}return 0;
}
/*
【trick&&吐槽】
1，排序的时候千万不要有
if(lastkey!=b.lastkey)return lastkey<b.lastkey
而要直接写成return lastkey<b.lastkey，否则会出错
2，正难则反的"变删除为添加"的思想很常见也很重要
3，这题还要考虑z==0是不可到达的点集（虽然数据中没有这样的）【题意】
我的世界游戏
建筑可以在地上或者与其它建筑连起来，而且不能完全封闭要与外界极远点相通。
问你一个建筑书序是否合法【类型】
正难则反 并查集【分析】
地图很小，可以直接维护100*100*100的所有点
每个方格的放置也就意味着有些点之间的联系被打断。
"联系被打断"不是很好处理，我们正难则反，从最后状态开始向前倒序处理。
一个格子的撤回就变成了关系的连通性。
每个格子都要与极外点（如101*101*101）联通【时间复杂度&&优化】
O(1e6)*/

这篇关于【hihocoder1291 微软2016校园招聘4月在线笔试D】【逆序思维 并查集】Buiding in Sandbox 我的世界建方块合法性判定的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---