#include "stdafx.h"
#include<iostream>
#include <iostream>
#include <fstream>
#include <string>





using namespace std;
int MAX = 50;
const int MacierzMax = 50;
int macierzRobocza[MacierzMax + 1][MacierzMax + 1];
int minIloscMacierzRobocza = 0;
int wynik[MacierzMax + 1][MacierzMax + 1];
int minIloscWynik = 0;


/*

Macierz jest wypełniona nastepującymi liczbami
-1    - pole nieuzupełnione
0     - pole usupełnione
0 < n - lewy górny róg (długość wstawionego kwadratu)

*/

void kopiujMacierz()
{
	minIloscWynik = 0;
	for (int i = 1; i <= MAX; i++)
	{
		for (int j = 1; j <= MAX; j++)
		{
			if (macierzRobocza[i][j] > 0) {
				minIloscWynik++;
			}
			wynik[i][j] = macierzRobocza[i][j];
		}
	}
}

// Wypełniam kwadrat kwadratem Max - 1
// Generuje pustą macierz
void generujMacierz()
{
	for (int i = 1; i <= MAX; i++)
	{
		for (int j = 1; j <= MAX; j++)
			macierzRobocza[i][j] = -1;
	}
}


void dodajBadanyKwadrat(int dlKwadratu)
{
	for (int i = 1; i <= dlKwadratu; i++)
	{
		for (int j = 1; j <= dlKwadratu; j++)
		{
			macierzRobocza[i][j] = 0;
		}
	}
	macierzRobocza[1][1] = dlKwadratu;
}

// Wyświetlam macierz kwadratu
void wyswietlMacierz(int macierz[MacierzMax + 1][MacierzMax + 1])
{
	for (int i = 1; i <= MAX; i++)
	{
		for (int j = 1; j <= MAX; j++)
		{
			printf(" %d ", macierz[i][j]);
		}
		printf("\n");
	}
}


// Dodaje kwadrat do macierzy
void wstawKwadrat(int x, int y, int dl)
{
	int dlmin = dl - 1;

	for (int i = x; i <= x + dlmin; i++)
	{
		for (int j = y; j <= y + dlmin; j++)
		{
			macierzRobocza[i][j] = 0;
		}
	}
	macierzRobocza[x][y] = dl;
	// ustawiam kordy i zeruje reszte pól

}



void Poka(int macierz[MacierzMax + 1][MacierzMax + 1])
{
	for (int i = 1; i <= MAX; i++)
	{
		for (int j = 1; j <= MAX; j++)
		{
			if (macierz[i][j] > 0) {
				printf("x:%d, y:%d,  %d \n", i, j, macierz[i][j]);
			}
		}
	}
}


// Sprawdzam czy kwadrat jest wypełniony
bool sprawdzCzySaUzupelnionePola()

{
	minIloscMacierzRobocza = 0;
	for (int i = 1; i <= MAX; i++)
	{
		for (int j = 1; j <= MAX; j++)
		{
			if (macierzRobocza[i][j] < 0) // jeżeli dana komórka posiada wartość -1 tzn, że macierz nie jest uzupełniona
			{
				return false;
			}
			if (macierzRobocza[i][j] > 0) {
				minIloscMacierzRobocza++;
			}
		}

	}
	return true;
}
bool sprawdzCzyMoznaDodacKwadrat(int x, int y, int dl)
{

	int dlmin = dl - 1;
	// Sprawdzam czy kwadrat nie wyjdzie poza macierz
	if (((x + dlmin) > MAX) || ((y + dlmin) > MAX))
	{
		return false;
	}

	for (int i = x; i <= x + dlmin; i++)
	{
		for (int j = y; j <= y + dlmin; j++)
		{
			if (macierzRobocza[i][j] >= 0)
			{
				return false;
			}
		}

	}
	wstawKwadrat(x, y, dl);
	return true;
}

// Rekurencyjnie szukam kwadratu do wstawienia
int szukajKwadratuDoWstawienia(int dlkwadratuDoWstawienia)
{
	if (sprawdzCzySaUzupelnionePola())
	{
		return 0;
	}


	for (int i = 1; i <= MAX; i++)
	{
		for (int j = 1; j <= MAX; j++)
		{
			// Jeżeli pole nie jest zapełnione
			if (macierzRobocza[i][j] < 0)    // szukam pola pustego i sprawdzam czy w tym polu moge doda
			{
				sprawdzCzyMoznaDodacKwadrat(i, j, dlkwadratuDoWstawienia);
			}
		}
	}

	dlkwadratuDoWstawienia--;
	szukajKwadratuDoWstawienia(dlkwadratuDoWstawienia);
}


void znajdzMacierz() {
	minIloscWynik = 0;
	for (int i = MAX - 1; i > 0; i--)
	{
		generujMacierz();
		dodajBadanyKwadrat(i);
		szukajKwadratuDoWstawienia(MAX - 1);
		if (minIloscMacierzRobocza < minIloscWynik || (minIloscWynik == 0)) {
			kopiujMacierz();
		}

	}
	printf("\n\n Wynik dla N = %d", MAX);
	printf("\n Najmniejsza ilosc kwadratow: %d  \n\n", minIloscWynik);
	wyswietlMacierz(wynik);
	cout << endl;
	Poka(wynik);
}

int main()
{
	string line;
	ifstream myfile("example.txt");
	if (myfile)
	{
		while (getline(myfile, line))
		{
			int b = atoi(line.c_str());
			MAX = b;
			znajdzMacierz();
		}
		myfile.close();
	}
	else {
		cout << "\n cos nie działa  \n";
	}

	system("pause");

	return 0;
}