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.15 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>> size_square;
  22.  
  23.  
  24. void max_insert(int x, int y)
  25. {
  26. int size;
  27. for (size = 1; size <= figure.N - 1; size++)
  28. {
  29. if (y + size > figure.N)
  30. return;
  31.  
  32. if (x + size > figure.M)
  33. return;
  34.  
  35. for (int i = y; i < y + size; i++)
  36. for (int j = x; j < x + size; j++)
  37. {
  38. if (figure.rectangle[i][j] != 0)
  39. return;
  40. }
  41. size_square.push(make_pair(size, false));
  42. }
  43. }
  44.  
  45.  
  46. void clear(trio a)
  47. {
  48. figure.delivered -= a.size * a.size;
  49.  
  50. for (int i = a.y; i < a.y + a.size; i++)
  51. for (int j = a.x; j < a.x + a.size; j++)
  52. figure.rectangle[i][j] = 0;
  53. }
  54.  
  55.  
  56. void insert(int x, int y, int size, int color)
  57. {
  58. figure.delivered += size * size;
  59.  
  60. for (int i = y; i < y + size; i++)
  61. for (int j = x; j < x + size; j++)
  62. figure.rectangle[i][j] = color;
  63. }
  64.  
  65.  
  66. void print(){
  67. for (int i = 0; i < figure.N; i++) {
  68. for (int j = 0; j < figure.M; j++) {
  69. cout << figure.rectangle[i][j] << ' ';
  70. }
  71. cout << endl;
  72. }
  73. cout << endl;
  74. getchar();
  75. }
  76.  
  77.  
  78.  
  79. pair<int, int> tiling()
  80. {
  81. int x = 0, y = 0;
  82. int color = 1;
  83. int number_colorings = 0;
  84. int number_squares = figure.N * figure.M + 1;
  85. bool flag;
  86.  
  87. max_insert(x, y);
  88.  
  89. do{
  90. flag = false;
  91.  
  92. for (y = 0; y < figure.N; y++) {
  93. for (x = 0; x < figure.M; x++)
  94. {
  95. if (figure.rectangle[y][x] == 0)
  96. {
  97. flag = true;
  98.  
  99. if (size_square.top().second == true)
  100. max_insert(x, y);
  101.  
  102. insert(x, y, size_square.top().first, color);
  103. figure.coordinates.push(trio{x, y, size_square.top().first});
  104. size_square.top().second = true;
  105.  
  106. color++;
  107. //cout << "Insert"<< endl;
  108. //print();
  109. break;
  110. }
  111. }
  112. if (flag)
  113. break;
  114. }
  115.  
  116. if ( color - 1 == number_squares && figure.delivered != figure.M * figure.N)
  117. {
  118. while ( !size_square.empty() && size_square.top().second)
  119. {
  120. size_square.pop();
  121. clear(figure.coordinates.top());
  122. figure.coordinates.pop();
  123. color--;
  124.  
  125. //cout << "Dell"<< endl;
  126. //print();
  127. }
  128. }
  129.  
  130. if ( !size_square.empty() && figure.delivered == figure.M * figure.N)
  131. {
  132. if (number_squares == color - 1)
  133. {
  134. number_colorings++;
  135. } else{
  136. number_squares = color - 1;
  137. number_colorings = 1;
  138. }
  139.  
  140.  
  141. while ( size_square.top().second )
  142. {
  143. size_square.pop();
  144. clear(figure.coordinates.top());
  145. figure.coordinates.pop();
  146. color--;
  147.  
  148. //cout << "Dell"<< endl;
  149. //print();
  150. }
  151. }
  152. }while (!size_square.empty());
  153.  
  154. return make_pair(number_squares, number_colorings);
  155. }
  156.  
  157.  
  158.  
  159. int main() {
  160. pair <int, int> ans;
  161. cin >> figure.N >> figure.M;
  162.  
  163. if (figure.N > figure.M)
  164. {
  165. swap(figure.N, figure.M);
  166. }
  167.  
  168. figure.rectangle = new int * [figure.N];
  169.  
  170. for (int i = 0; i < figure.N; i++)
  171. {
  172. figure.rectangle[i] = new int[figure.M];
  173. }
  174.  
  175. for (int i = 0; i < figure.N; i++)
  176. for (int j = 0; j < figure.M; j++)
  177. {
  178. figure.rectangle[i][j] = 0;
  179. }
  180.  
  181. ans = tiling();
  182.  
  183. cout << "Minimum number of squares: " << ans.first << endl
  184. << "Number of minimum constellations: " << ans.second;
  185.  
  186. return 0;
  187. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement