Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.42 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <stack>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. struct Trio{
  9. int x;
  10. int y;
  11. int size;
  12. };
  13.  
  14. struct Figure {
  15. int** rectangle;
  16. int delivered;
  17. int N, M;
  18. stack <Trio> coordinates;
  19. } figure;
  20.  
  21. stack <pair<int, bool>> sizeSquare;
  22.  
  23. stack <Trio> ansCoordinates;
  24.  
  25.  
  26. void max_insert(int x, int y)
  27. {
  28. int size;
  29. for (size = 1; size <= figure.N - 1; size++)
  30. {
  31. if (y + size > figure.N)
  32. return;
  33.  
  34. if (x + size > figure.M)
  35. return;
  36.  
  37. for (int i = y; i < y + size; i++)
  38. for (int j = x; j < x + size; j++)
  39. {
  40. if (figure.rectangle[i][j] != 0)
  41. return;
  42. }
  43. sizeSquare.push(make_pair(size, false));
  44. }
  45. }
  46.  
  47.  
  48. void clear(Trio a)
  49. {
  50. figure.delivered -= a.size * a.size;
  51.  
  52. for (int i = a.y; i < a.y + a.size; i++)
  53. for (int j = a.x; j < a.x + a.size; j++)
  54. figure.rectangle[i][j] = 0;
  55. }
  56.  
  57.  
  58. void insert(int x, int y, int size, int color)
  59. {
  60. figure.delivered += size * size;
  61.  
  62. for (int i = y; i < y + size; i++)
  63. for (int j = x; j < x + size; j++)
  64. figure.rectangle[i][j] = color;
  65. }
  66.  
  67.  
  68. void print(){
  69. for (int i = 0; i < figure.N; i++) {
  70. for (int j = 0; j < figure.M; j++) {
  71. cout << figure.rectangle[i][j] << ' ';
  72. }
  73. cout << endl;
  74. }
  75. cout << endl;
  76. getchar();
  77. }
  78.  
  79.  
  80.  
  81. pair<int, int> tiling()
  82. {
  83. int x = 0, y = 0;
  84. int color = 1;
  85. int numberColorings = 0;
  86. int numberSquares = figure.N * figure.M + 1;
  87. bool flag;
  88.  
  89. max_insert(x, y);
  90.  
  91. do{
  92. flag = false;
  93.  
  94. for (y = 0; y < figure.N; y++) {
  95. for (x = 0; x < figure.M; x++)
  96. {
  97. if (figure.rectangle[y][x] == 0)
  98. {
  99. flag = true;
  100.  
  101. if (sizeSquare.top().second == true)
  102. max_insert(x, y);
  103.  
  104. insert(x, y, sizeSquare.top().first, color);
  105. figure.coordinates.push(Trio{x, y, sizeSquare.top().first});
  106. sizeSquare.top().second = true;
  107.  
  108. color++;
  109. //cout << "Insert"<< endl;
  110. //print();
  111. break;
  112. }
  113. }
  114. if (flag)
  115. break;
  116. }
  117.  
  118. if ( color - 1 == numberSquares && figure.delivered != figure.M * figure.N)
  119. {
  120. while ( !sizeSquare.empty() && sizeSquare.top().second)
  121. {
  122. sizeSquare.pop();
  123. clear(figure.coordinates.top());
  124. figure.coordinates.pop();
  125. color--;
  126.  
  127. //cout << "Dell"<< endl;
  128. //print();
  129. }
  130. }
  131.  
  132. if ( !sizeSquare.empty() && figure.delivered == figure.M * figure.N)
  133. {
  134. if (numberSquares == color - 1)
  135. {
  136. numberColorings++;
  137. } else{
  138. ansCoordinates = figure.coordinates;
  139. numberSquares = color - 1;
  140. numberColorings = 1;
  141. }
  142.  
  143.  
  144. while ( sizeSquare.top().second )
  145. {
  146. sizeSquare.pop();
  147. clear(figure.coordinates.top());
  148. figure.coordinates.pop();
  149. color--;
  150.  
  151. //cout << "Dell"<< endl;
  152. //print();
  153. }
  154. }
  155. }while (!sizeSquare.empty());
  156.  
  157. return make_pair(numberSquares, numberColorings);
  158. }
  159.  
  160.  
  161.  
  162. int main() {
  163. pair <int, int> ans;
  164. cin >> figure.N >> figure.M;
  165.  
  166. if (figure.N > figure.M)
  167. {
  168. swap(figure.N, figure.M);
  169. }
  170.  
  171. figure.rectangle = new int * [figure.N];
  172.  
  173. for (int i = 0; i < figure.N; i++)
  174. {
  175. figure.rectangle[i] = new int[figure.M];
  176. }
  177.  
  178. for (int i = 0; i < figure.N; i++)
  179. for (int j = 0; j < figure.M; j++)
  180. {
  181. figure.rectangle[i][j] = 0;
  182. }
  183.  
  184. ans = tiling();
  185.  
  186. cout << "Minimum number of squares: " << ans.first << endl
  187. << "Number of minimum constellations: " << ans.second << endl;
  188.  
  189. for (int i = 0; i < ans.first; i++)
  190. {
  191. cout << ansCoordinates.top().x << ' ' << ansCoordinates.top().y << ' ' << ansCoordinates.top().size << endl;
  192. ansCoordinates.pop();
  193. }
  194.  
  195. return 0;
  196. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement