Building in Sandbox

<vector> #include<deque> #include<stack> #include<string> #include<algorithm> #include<string.h> #include<sstream> struct Point { int x, y, z; Point() : x(0), y(0), z(0) {}; Point(int a, int b, int c) : x(a), y(b), z(c) {} }; int MAX_C; const int MAX_N = 100000+5; const int dir[6][3] = { {1, 0, 0}, {0, 1, 0}, {0, 0, 1}, {-1, 0, 0}, {0, -1, 0}, {0, 0, -1} }; int pos[100 + 2][100 + 2][100 + 2]; int is_out[100 + 2][100 + 2][100 + 2]; Point cors[MAX_N]; using namespace std; bool has_adj(int x, int y, int z) { if (z == 1) return true; for (int d = 0; d < 6; ++d) { int x1 = x + dir[d][0]; int y1 = y + dir[d][1]; int z1 = z + dir[d][2]; if (pos[x1][y1][z1]) return true; } return false; } bool can_take(int x, int y, int z) { for (int d = 0; d < 6; ++d) { int x1 = x + dir[d][0]; int y1 = y + dir[d][1]; int z1 = z + dir[d][2]; if (is_out[x1][y1][z1]) return true; } return false; } void my_bfs(int x, int y, int z) { deque<Point> q; Point p0(x, y, z); q.push_back(p0); while (!q.empty()) { Point p = q[0]; q.pop_front(); if (p.z < 1 || p.z > MAX_C + 1 || p.x < 0 || p.x > MAX_C + 1 || p.y < 0 || p.y > MAX_C + 1) continue; if (is_out[p.x][p.y][p.z] || pos[p.x][p.y][p.z]) continue; is_out[p.x][p.y][p.z] = 1; for (int d = 0; d < 6; ++d) { int x1 = p.x + dir[d][0]; int y1 = p.y + dir[d][1]; int z1 = p.z + dir[d][2]; Point p1(x1, y1, z1); q.push_back(p1); } } } int main() { int T; cin >> T; for (int t = 0; t < T; ++t) { int N; cin >> N; memset(pos, 0, sizeof(pos)); memset(is_out, 0, sizeof(is_out)); bool is_possible = true; MAX_C = 0; for (int i = 0; i < N; ++i) { int x, y, z; cin >> x >> y >> z; cors[i].x = x; cors[i].y = y; cors[i].z = z; MAX_C = max(x, MAX_C); MAX_C = max(y, MAX_C); MAX_C = max(z, MAX_C); if (!pos[x][y][z] && has_adj(x, y, z)) { pos[x][y][z] = 1; } else { is_possible = false; //break; } } if (!is_possible) { cout << "No" << endl; continue; } else { my_bfs(0, 0, 1); for (int i = N - 1; i >= 0; --i) { int x = cors[i].x; int y = cors[i].y; int z = cors[i].z; if (!can_take(x, y, z)) { is_possible = false; break; } pos[x][y][z] = 0; my_bfs(x, y, z); } if (is_possible) cout << "Yes" << endl; else cout << "No" << endl; } } //system("pause"); return 0; }

 

Building in Sandbox

标签：cas   分享   检查   main   passing   tca   查看   ssi   顺序