fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct Cube {
  5. int X, Y, Z;
  6. vector<vector<vector<int>>> a;
  7. };
  8.  
  9. int nTests;
  10.  
  11. // Tính số ô 1 còn lại
  12. int countOnes(const Cube &c) {
  13. int cnt = 0;
  14. for (int i = 0; i < c.X; i++)
  15. for (int j = 0; j < c.Y; j++)
  16. for (int k = 0; k < c.Z; k++)
  17. if (c.a[i][j][k] == 1)
  18. cnt++;
  19. return cnt;
  20. }
  21.  
  22. // Tìm hình chữ nhật toàn 1 lớn nhất trong ma trận 2D (O(n*m))
  23. pair<int, array<int,4>> largestRectangle2D(const vector<vector<int>> &mat) {
  24. int n = mat.size();
  25. if (n == 0) return {0, {0,0,0,0}};
  26. int m = mat[0].size();
  27. vector<int> h(m, 0);
  28. int best = 0;
  29. array<int,4> bestPos = {0,0,0,0};
  30. for (int i = 0; i < n; i++) {
  31. for (int j = 0; j < m; j++)
  32. h[j] = (mat[i][j] == 0 ? 0 : h[j] + 1);
  33. // tính largest rectangle in histogram
  34. stack<int> st;
  35. int j = 0;
  36. while (j < m) {
  37. if (st.empty() || h[st.top()] <= h[j]) st.push(j++);
  38. else {
  39. int tp = st.top(); st.pop();
  40. int width = st.empty() ? j : j - st.top() - 1;
  41. int area = h[tp] * width;
  42. if (area > best) {
  43. best = area;
  44. bestPos = {i - h[tp] + 1, (st.empty()?0:st.top()+1), i, j-1};
  45. }
  46. }
  47. }
  48. while (!st.empty()) {
  49. int tp = st.top(); st.pop();
  50. int width = st.empty() ? j : j - st.top() - 1;
  51. int area = h[tp] * width;
  52. if (area > best) {
  53. best = area;
  54. bestPos = {i - h[tp] + 1, (st.empty()?0:st.top()+1), i, j-1};
  55. }
  56. }
  57. }
  58. return {best, bestPos};
  59. }
  60.  
  61. int solveOne(Cube c) {
  62. int cost = 0;
  63. int remaining = countOnes(c);
  64. if (remaining == 0) return 0;
  65. if (remaining == c.X * c.Y * c.Z) return min({c.X, c.Y, c.Z});
  66.  
  67. while (remaining > 0) {
  68.     int bestCount = 0;
  69.     int bestAxis = 0; // 0=fix X, 1=fix Y, 2=fix Z
  70.     int idx = -1;
  71.     array<int,4> rect{0,0,0,0};
  72.  
  73.     // check từng layer fix X
  74.     for (int i = 0; i < c.X; i++) {
  75.         vector<vector<int>> layer(c.Y, vector<int>(c.Z));
  76.         for (int j = 0; j < c.Y; j++)
  77.             for (int k = 0; k < c.Z; k++)
  78.                 layer[j][k] = c.a[i][j][k];
  79.         auto [cnt, pos] = largestRectangle2D(layer);
  80.         if (cnt > bestCount) {
  81.             bestCount = cnt;
  82.             bestAxis = 0; idx = i; rect = pos;
  83.         }
  84.     }
  85.  
  86.     // check từng layer fix Y
  87.     for (int j = 0; j < c.Y; j++) {
  88.         vector<vector<int>> layer(c.X, vector<int>(c.Z));
  89.         for (int i = 0; i < c.X; i++)
  90.             for (int k = 0; k < c.Z; k++)
  91.                 layer[i][k] = c.a[i][j][k];
  92.         auto [cnt, pos] = largestRectangle2D(layer);
  93.         if (cnt > bestCount) {
  94.             bestCount = cnt;
  95.             bestAxis = 1; idx = j; rect = pos;
  96.         }
  97.     }
  98.  
  99.     // check từng layer fix Z
  100.     for (int k = 0; k < c.Z; k++) {
  101.         vector<vector<int>> layer(c.X, vector<int>(c.Y));
  102.         for (int i = 0; i < c.X; i++)
  103.             for (int j = 0; j < c.Y; j++)
  104.                 layer[i][j] = c.a[i][j][k];
  105.         auto [cnt, pos] = largestRectangle2D(layer);
  106.         if (cnt > bestCount) {
  107.             bestCount = cnt;
  108.             bestAxis = 2; idx = k; rect = pos;
  109.         }
  110.     }
  111.  
  112.     if (bestCount == 0) break; // không tìm thấy gì (chỉ còn rải rác)
  113.  
  114.     // Xóa vùng đã chọn (set = 0)
  115.     if (bestAxis == 0) { // fix X = idx
  116.         for (int j = rect[0]; j <= rect[2]; j++)
  117.             for (int k = rect[1]; k <= rect[3]; k++)
  118.                 if (c.a[idx][j][k]) {
  119.                     c.a[idx][j][k] = 0;
  120.                     remaining--;
  121.                 }
  122.     } else if (bestAxis == 1) { // fix Y = idx
  123.         for (int i = rect[0]; i <= rect[2]; i++)
  124.             for (int k = rect[1]; k <= rect[3]; k++)
  125.                 if (c.a[i][idx][k]) {
  126.                     c.a[i][idx][k] = 0;
  127.                     remaining--;
  128.                 }
  129.     } else { // fix Z = idx
  130.         for (int i = rect[0]; i <= rect[2]; i++)
  131.             for (int j = rect[1]; j <= rect[3]; j++)
  132.                 if (c.a[i][j][idx]) {
  133.                     c.a[i][j][idx] = 0;
  134.                     remaining--;
  135.                 }
  136.     }
  137.     cost++;
  138. }
  139.  
  140. return cost;
  141.  
  142.  
  143. }
  144.  
  145. int main() {
  146. ios::sync_with_stdio(false);
  147. cin.tie(nullptr);
  148. cin >> nTests;
  149. while (nTests--) {
  150. Cube c;
  151. cin >> c.X >> c.Y >> c.Z;
  152. c.a.assign(c.X, vector<vector<int>>(c.Y, vector<int>(c.Z)));
  153. for (int i = 0; i < c.X; i++)
  154. for (int j = 0; j < c.Y; j++) {
  155. string s; cin >> s;
  156. for (int k = 0; k < c.Z; k++)
  157. c.a[i][j][k] = s[k] - '0';
  158. }
  159. cout << solveOne(c) << "\n";
  160. }
  161. return 0;
  162. }
  163.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin 
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 
1
https://ideone.com/cRuxx0
language:
C++14 (gcc 8.3)
created:
3 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!