fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Node {
  5. int x, y, z;
  6. };
  7.  
  8. int main() {
  9. ios::sync_with_stdio(false);
  10. cin.tie(nullptr);
  11.  
  12.  
  13. int T;
  14. cin >> T;
  15. while (T--) {
  16.     int X, Y, Z;
  17.     cin >> X >> Y >> Z;
  18. swap(X,Z );
  19.     // grid[z][x][y] để nhất quán với (i,j,k)
  20.     vector<vector<vector<int>>> grid(Z, vector<vector<int>>(X, vector<int>(Y)));
  21.     for (int k = 0; k < Z; ++k) {
  22.         for (int i = 0; i < X; ++i) {
  23.             string s;
  24.             cin >> s;
  25.             for (int j = 0; j < Y; ++j)
  26.                 grid[k][i][j] = s[j] - '0';
  27.         }
  28.     }
  29.  
  30.     vector<vector<vector<bool>>> vis(Z, vector<vector<bool>>(X, vector<bool>(Y, false)));
  31.     int total = 0;
  32.  
  33.     int dx[6] = {1, -1, 0, 0, 0, 0};
  34.     int dy[6] = {0, 0, 1, -1, 0, 0};
  35.     int dz[6] = {0, 0, 0, 0, 1, -1};
  36.  
  37.     for (int k = 0; k < Z; ++k)
  38.         for (int i = 0; i < X; ++i)
  39.             for (int j = 0; j < Y; ++j)
  40.                 if (grid[k][i][j] == 1 && !vis[k][i][j]) {
  41.                     // BFS để tìm khối liên thông
  42.                     queue<Node> q;
  43.                     q.push({i, j, k});
  44.                     vis[k][i][j] = true;
  45.  
  46.                     int minx = i, maxx = i;
  47.                     int miny = j, maxy = j;
  48.                     int minz = k, maxz = k;
  49.  
  50.                     while (!q.empty()) {
  51.                         Node cur = q.front();
  52.                         q.pop();
  53.                         for (int d = 0; d < 6; ++d) {
  54.                             int nx = cur.x + dx[d];
  55.                             int ny = cur.y + dy[d];
  56.                             int nz = cur.z + dz[d];
  57.                             if (nx >= 0 && nx < X && ny >= 0 && ny < Y && nz >= 0 && nz < Z) {
  58.                                 if (!vis[nz][nx][ny] && grid[nz][nx][ny] == 1) {
  59.                                     vis[nz][nx][ny] = true;
  60.                                     q.push({nx, ny, nz});
  61.                                     minx = min(minx, nx);
  62.                                     maxx = max(maxx, nx);
  63.                                     miny = min(miny, ny);
  64.                                     maxy = max(maxy, ny);
  65.                                     minz = min(minz, nz);
  66.                                     maxz = max(maxz, nz);
  67.                                 }
  68.                             }
  69.                         }
  70.                     }
  71.  
  72.                     int a = maxx - minx + 1;
  73.                     int b = maxy - miny + 1;
  74.                     int c = maxz - minz + 1;
  75.                     total += min({a, b, c});
  76.                 }
  77.  
  78.     cout << total << "\n";
  79. }
  80. return 0;
  81.  
  82.  
  83. }
  84.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
stdout
copy 
2
https://ideone.com/GTHdKo
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!