Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <stack>
- using namespace std;
- struct Trio{
- int x;
- int y;
- int size;
- };
- struct Figure {
- int** rectangle;
- int delivered;
- int N, M;
- stack <Trio> coordinates;
- } figure;
- stack <pair<int, bool>> sizeSquare;
- stack <Trio> ansCoordinates;
- void max_insert(int x, int y)
- {
- int size;
- for (size = 1; size <= figure.N - 1; size++)
- {
- if (y + size > figure.N)
- return;
- if (x + size > figure.M)
- return;
- for (int i = y; i < y + size; i++)
- for (int j = x; j < x + size; j++)
- {
- if (figure.rectangle[i][j] != 0)
- return;
- }
- sizeSquare.push(make_pair(size, false));
- }
- }
- void clear(Trio a)
- {
- figure.delivered -= a.size * a.size;
- for (int i = a.y; i < a.y + a.size; i++)
- for (int j = a.x; j < a.x + a.size; j++)
- figure.rectangle[i][j] = 0;
- }
- void insert(int x, int y, int size, int color)
- {
- figure.delivered += size * size;
- for (int i = y; i < y + size; i++)
- for (int j = x; j < x + size; j++)
- figure.rectangle[i][j] = color;
- }
- void print(){
- for (int i = 0; i < figure.N; i++) {
- for (int j = 0; j < figure.M; j++) {
- cout << figure.rectangle[i][j] << ' ';
- }
- cout << endl;
- }
- cout << endl;
- getchar();
- }
- pair<int, int> tiling()
- {
- int x = 0, y = 0;
- int color = 1;
- int numberColorings = 0;
- int numberSquares = figure.N * figure.M + 1;
- bool flag;
- max_insert(x, y);
- do{
- flag = false;
- for (y = 0; y < figure.N; y++) {
- for (x = 0; x < figure.M; x++)
- {
- if (figure.rectangle[y][x] == 0)
- {
- flag = true;
- if (sizeSquare.top().second == true)
- max_insert(x, y);
- insert(x, y, sizeSquare.top().first, color);
- figure.coordinates.push(Trio{x, y, sizeSquare.top().first});
- sizeSquare.top().second = true;
- color++;
- //cout << "Insert"<< endl;
- //print();
- break;
- }
- }
- if (flag)
- break;
- }
- if ( color - 1 == numberSquares && figure.delivered != figure.M * figure.N)
- {
- while ( !sizeSquare.empty() && sizeSquare.top().second)
- {
- sizeSquare.pop();
- clear(figure.coordinates.top());
- figure.coordinates.pop();
- color--;
- //cout << "Dell"<< endl;
- //print();
- }
- }
- if ( !sizeSquare.empty() && figure.delivered == figure.M * figure.N)
- {
- if (numberSquares == color - 1)
- {
- numberColorings++;
- } else{
- ansCoordinates = figure.coordinates;
- numberSquares = color - 1;
- numberColorings = 1;
- }
- while ( sizeSquare.top().second )
- {
- sizeSquare.pop();
- clear(figure.coordinates.top());
- figure.coordinates.pop();
- color--;
- //cout << "Dell"<< endl;
- //print();
- }
- }
- }while (!sizeSquare.empty());
- return make_pair(numberSquares, numberColorings);
- }
- int main() {
- pair <int, int> ans;
- cin >> figure.N >> figure.M;
- if (figure.N > figure.M)
- {
- swap(figure.N, figure.M);
- }
- figure.rectangle = new int * [figure.N];
- for (int i = 0; i < figure.N; i++)
- {
- figure.rectangle[i] = new int[figure.M];
- }
- for (int i = 0; i < figure.N; i++)
- for (int j = 0; j < figure.M; j++)
- {
- figure.rectangle[i][j] = 0;
- }
- ans = tiling();
- cout << "Minimum number of squares: " << ans.first << endl
- << "Number of minimum constellations: " << ans.second << endl;
- for (int i = 0; i < ans.first; i++)
- {
- cout << ansCoordinates.top().x << ' ' << ansCoordinates.top().y << ' ' << ansCoordinates.top().size << endl;
- ansCoordinates.pop();
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement