SHARE
TWEET

Untitled

a guest Feb 24th, 2020 68 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top