// Function: To determine the number of equivalence classes of ways of placing k square tiles with side length s in an A X B rectangle, B <= A,
//           under all symmetry operations of the rectangle.
//
// Developed by Chris Gribble in 2014 as a console project under Microsoft Visual Studio Express 2013.
//
// The version of the program uploaded to the OEIS compiles with g++ (gcc 4.5.2).

using namespace std;

#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>
#include <string>

static const int MaxA        = 30;					// Maximum value of A.
static const int MaxB		 = 30;					// Maximum value of B.
static const int MaxS		 = 8000000;				// Maximum number of boundary rectangles in tree.
static const int MinA        = 0;					// Minimum value of A.
static const int MinB		 = 0;					// Minimum value of B.

static __int64 NumMatchIdentity[MaxA];				// Number of partially tiled boundary rectangles generated that match others in the tree.
static __int64 NumMatchless[MaxA];					// Number of partially tiled boundary rectangles in tree.
static __int64 NumMatchReflectHoriz[MaxA];			// Number of partially tiled boundary rectangles generated that, when reflected about the horizontal axis, match others in the tree.
static __int64 NumMatchReflectVert[MaxA];			// Number of partially tiled boundary rectangles generated that, when reflected about the vertical axis, match others in the tree.
static __int64 NumMatchRotate180[MaxA];				// Number of partially tiled boundary rectangles generated that, when rotated by 180 degs, match others in the tree.

static int LevelFirstIndex[MaxA * MaxB];			// Index of first boundary rectangle at each level in tree.
static int LevelLastIndex[MaxA * MaxB];				// Index of last boundary rectangle at each level in tree.
static int RectangleIndex;							// Index of boundary rectangle in the list of partially tiled boundary rectangles.

static short int A;									// User-specified boundary rectangle side length.
static short int AB;								// A * B.
static short int B;									// User-specified boundary rectangle side length.
static short int Level;								// Current level in tree = number of square tiles placed in boundary rectangle.
static short int MaxNumTiles;						// Maximum number of tiles to be placed in boundary rectangle to limit computation.
static short int MinTileSideSize;					// Minimum tile side size to reduce excessive computation.
static short int NumTreesBuilt;						// Number of trees built.
static short int Rectangle[MaxA][MaxB];				// Boundary rectangle.

static short int ***ListOfRectangles;				// List of all partially tiled boundary rectangles with symmetries removed.

fstream OpFile;										// Output file.


bool matchTransformations()
{
	// Indicates whether transform of the boundary rectangle pre-exists or not.

	int n;										// Loop counter.

	short int k, l;								// Loop counters.
	short int match_identity;					// Count of cell value matches between a new boundary rectangle and previously generated boundary rectangles at the same level.
	short int match_reflect_horiz;				// Count of cell value matches between a new boundary rectangle reflected about the horizontal axis and previously generated boundary rectangles at the same level.
	short int match_reflect_vert;				// Count of cell value matches between a new boundary rectangle reflected about the vertical axis and previously generated boundary rectangles at the same level.
	short int match_rotate_180;					// Count of cell value matches between a new boundary rectangle rotated by 180 degs and previously generated boundary rectangles at the same level.

	bool transformExists = false;				// Indicates whether a transform of a new boundary rectangle already exists at the same level or not.

	// Check that a transformation of this rectangle does not already exist at the same level.

	for (n = LevelFirstIndex[Level]; n < RectangleIndex; n++)
	{
		match_identity      = 0;
		match_reflect_horiz = 0;
		match_reflect_vert  = 0;
		match_rotate_180    = 0;

		for (l = 0; l < B; l++)
		{
			for (k = 0; k < A; k++)
			{
				// Identity transformation.

				if (Rectangle[k][l] == ListOfRectangles[n][k][l])
				{
					match_identity++;
				}

				// Reflect horizontally.

				if (Rectangle[A - k - 1][l] == ListOfRectangles[n][k][l])
				{
					match_reflect_horiz++;
				}

				// Reflect vertically.

				if (Rectangle[k][B - l - 1] == ListOfRectangles[n][k][l])
				{
					match_reflect_vert++;
				}

				// Rotate left by 180 degs.

				if (Rectangle[A - k - 1][B - l - 1] == ListOfRectangles[n][k][l])
				{
					match_rotate_180++;
				}
			}
		}

		if (match_identity == AB)
		{
			NumMatchIdentity[NumTreesBuilt]++;
			transformExists = true;
			// OpFile << "NumMatchIdentity     = " << NumMatchIdentity[NumTreesBuilt] << endl << endl;
			break;
		}
		else if (match_reflect_horiz == AB)
		{
			NumMatchReflectHoriz[NumTreesBuilt]++;
			transformExists = true;
			// OpFile << "NumMatchReflectHoriz = " << NumMatchReflectHoriz[NumTreesBuilt] << endl << endl;
			break;
		}
		else if (match_reflect_vert == AB)
		{
			NumMatchReflectVert[NumTreesBuilt]++;
			transformExists = true;
			// OpFile << "NumMatchReflectVert  = " << NumMatchReflectVert[NumTreesBuilt] << endl << endl;
			break;
		}
		else if (match_rotate_180 == AB)
		{
			NumMatchRotate180[NumTreesBuilt]++;
			transformExists = true;
			// OpFile << "NumMatchRotate180    = " << NumMatchRotate180[NumTreesBuilt] << endl << endl;
			break;
		}
	}

	if (transformExists == false)
	{
		NumMatchless[NumTreesBuilt]++;
		// OpFile << "NumMatchless         = " << NumMatchless[NumTreesBuilt] << endl << endl;
	}

	return transformExists;
}

void buildTree()
{
	int m;										// Loop counter.

	short int empty;
	short int flagRectangle[MaxA][MaxB];		// Records which cells have been used when trying to place the top left hand corner of a square tile other than the first.
	short int i, j, k, l;						// Loop counters.
	short int numPartsFitted = 0;
	short int numTiles;
	short int s, t;
	short int tileSize;
	short int x, y;

	bool emptyCell;								// Indicates whether an empty cell has been found in the boundary rectangle or not.
	bool firstTile;								// Indicates whether the first tile at a particular level has been placed or not.
	bool transformExists;						// Indicates whether a transform of a new boundary rectangle already exists at the same level or not.

	for (tileSize = MinTileSideSize; tileSize <= B; tileSize++)
	{
		// Increment number of trees built.

		NumTreesBuilt++;
		// OpFile << endl << "Number of trees built = " << NumTreesBuilt << endl;
		OpFile << endl << "Tile side length      = " << NumTreesBuilt + MinTileSideSize - 1 << endl;

		// Construct tree.

		// Initialisations.

		for (i = 0; i <= AB; i++)
		{
			LevelFirstIndex[i] = 0;
			LevelLastIndex[i]  = 0;
		}

		// Form boundary rectangle at Level 0.

		Level = 0;
		RectangleIndex = 0;
		LevelFirstIndex[Level] = RectangleIndex;
		LevelLastIndex[Level]  = RectangleIndex;

		for (j = 0; j < B; j++)
		{
			for (i = 0; i < A; i++)
			{
				ListOfRectangles[RectangleIndex][i][j] = 0;
			}
		}

		// Form boundary rectangles at Level 1.
		// Place the top left hand corner of the largest square tile in each of the positions within the top left hand quarter of the boundary rectangle.

		s = (A - tileSize) / 2 + 1;
		t = (B - tileSize) / 2 + 1;

		Level++;

		for (y = 0; y < t; y++)
		{
			for (x = 0; x < s; x++)
			{
				// Initialise rectangle.

				for (j = 0; j < B; j++)
				{
					for (i = 0; i < A; i++)
					{
						Rectangle[i][j] = ListOfRectangles[LevelFirstIndex[Level - 1]][i][j];
					}
				}

				for (j = y; j < y + tileSize; j++)
				{
					for (i = x; i < x + tileSize; i++)
					{
						Rectangle[i][j] = tileSize;
					}
				}
				/*
				for (j = 0; j < B; j++)
				{
					for (i = 0; i < A; i++)
					{
						OpFile << " " << Rectangle[i][j];
					}

					OpFile << endl;
				}

				OpFile << endl;
				*/
				// Record square.

				RectangleIndex++;

				if ((x == 0) &&
					(y == 0))
				{
					LevelFirstIndex[Level] = RectangleIndex;
				}

				for (j = 0; j < B; j++)
				{
					for (i = 0; i < A; i++)
					{
						ListOfRectangles[RectangleIndex][i][j] = Rectangle[i][j];
					}
				}

				LevelLastIndex[Level] = RectangleIndex;
			}
		}

		// Form rectangles at other levels.

		numTiles = (A / tileSize) * (B / tileSize);

		if (numTiles > MaxNumTiles) numTiles = MaxNumTiles;

		for (i = 2; i <= numTiles; i++)
		{
			Level++;
			firstTile = false;

			for (m = LevelFirstIndex[Level - 1]; m <= LevelLastIndex[Level - 1]; m++)
			{
				// Record which cells cannot be used to place new part.

				for (l = 0; l < B; l++)
				{
					for (k = 0; k < A; k++)
					{
						flagRectangle[k][l] = ListOfRectangles[m][k][l];
					}
				}

				// Find the next empty cell in the rectangle.

findNextEmptyCell:

				emptyCell = false;

				for (l = 0; l < B; l++)
				{
					for (k = 0; k < A; k++)
					{
						if (flagRectangle[k][l] == 0)
						{
							emptyCell = true;
							x = l;
							y = k;
							break;
						}
					}

					if (emptyCell == true) break;
				}

				if (emptyCell == true)
				{
					// Try to fit part into rectangle with the empty cell corresponding to the top left-hand corner of the part.

					if ((y + tileSize <= A) &&
						(x + tileSize <= B))
					{
						empty = 0;

						for (l = x; l < x + tileSize; l++)
						{
							for (k = y; k < y + tileSize; k++)
							{
								if (flagRectangle[k][l] == 0)
								{
									empty++;
								}
							}
						}

						if (empty == tileSize * tileSize)
						{
							// Part fits, so fit it.

							RectangleIndex++;

							if (firstTile == false)
							{
								LevelFirstIndex[Level] = RectangleIndex;
								firstTile = true;
							}

							for (l = 0; l < B; l++)
							{
								for (k = 0; k < A; k++)
								{
									Rectangle[k][l] = ListOfRectangles[m][k][l];
								}
							}

							for (l = x; l < x + tileSize; l++)
							{
								for (k = y; k < y + tileSize; k++)
								{
									Rectangle[k][l] = tileSize;
								}
							}
							/*
							for (l = 0; l < B; l++)
							{
								for (k = 0; k < A; k++)
								{
									OpFile << " " << Rectangle[k][l];
								}

								OpFile << endl;
							}

							OpFile << endl;
							*/
							// Check that a transformation of this rectangle does not already exist at this level.

							transformExists = matchTransformations();

							if (transformExists == true)
							{
								flagRectangle[y][x] = -4;				// Set flag to indicate that a fit was successful at this cell, but do not put boundary rectangle in list.
								RectangleIndex--;
								goto findNextEmptyCell;
							}

							for (l = 0; l < B; l++)
							{
								for (k = 0; k < A; k++)
								{
									ListOfRectangles[RectangleIndex][k][l] = Rectangle[k][l];
								}
							}

							flagRectangle[y][x] = -2;						// Flag fit successful at this cell.
							LevelLastIndex[Level] = RectangleIndex;
							cout << NumTreesBuilt << "    " << Level << "    " << RectangleIndex << "    " << m << "    " << LevelLastIndex[Level - 1] << endl;
							/*
							for (l = 0; l < B; l++)
							{
								for (k = 0; k < A; k++)
								{
									OpFile << " " << Rectangle[k][l];
								}

								OpFile << "    ";

								for (k = 0; k < A; k++)
								{
									OpFile << " " << flagRectangle[k][l];
								}

								OpFile << endl;
							}

							OpFile << endl;
							*/
							// Find where the square tile can fit next.

							goto findNextEmptyCell;
						}
						else
						{
							// Part doesn't fit, so find the next empty cell if there is one.

							flagRectangle[y][x] = -1;					// Set flag to indicate that a fit was unsuccessful at this cell.
							goto findNextEmptyCell;
						}
					}
					else
					{
						// Part doesn't fit, so find the next empty cell if there is one.

						flagRectangle[y][x] = -1;						// Set flag to indicate that a fit was unsuccessful at this cell.
						goto findNextEmptyCell;
					}
				}		// End of if.
			}		// End of m loop.

			if (LevelLastIndex[Level] == 0)
			{
				// No part could be fitted at the current level.

				break;
			}
		}		// End of i loop.

		// Output level data.

		for (l = 0; l <= Level; l++)
		{
			OpFile << l << "    " << LevelLastIndex[l] - LevelFirstIndex[l] + 1 << endl;
		}
	}		// 	End of for (tileSize = 1; tileSize <= N; tileSize++)

	return;
}


int main()
{
	int  i, j;							// Loop counters.

	// Create output file.

	OpFile.open("SquarePlacementsInRectangle.txt", ios_base::out | ios_base::trunc);

	// Get dimensions of rectangle.

	cout << "Enter A ";
	cin >> A;

	if ((A < MinA) ||
		(A > MaxA))
	{
		OpFile << "Value of A " << A << " out of range." << endl;
		return 1;
	}

	OpFile << "A = " << A << endl;

	cout << "Enter B ";
	cin >> B;

	if ((B < MinB) ||
		(B > MaxB) ||
		(B > A))
	{
		OpFile << "Value of B " << B << " out of range." << endl;
		return 1;
	}

	OpFile << "B = " << B << endl;

	AB = A * B;

	cout << "Enter minimum tile side size ";
	cin >> MinTileSideSize;

	if ((MinTileSideSize < 1) ||
		(MinTileSideSize > B))
	{
		OpFile << "Value of MinTileSideSize " << MinTileSideSize << " out of range." << endl;
		return 1;
	}

	cout << "Enter maximum number of tiles to be placed ";
	cin >> MaxNumTiles;

	if (MaxNumTiles < 1)
	{
		OpFile << "Value of MaxNumTiles " << MaxNumTiles << " out of range." << endl;
		return 1;
	}
	else if (MaxNumTiles > (A / MinTileSideSize) * (B / MinTileSideSize))
	{
		MaxNumTiles = (A / MinTileSideSize) * (B / MinTileSideSize);
	}

	// Allocate memory for list of squares for use in buildTree.

	ListOfRectangles = (short int ***)malloc(MaxS * sizeof(short int **));

	for (i = 0; i < MaxS; i++)
	{
		ListOfRectangles[i] = (short int **)malloc(A * sizeof(short int *));
	}

	for (j = 0; j < A; j++)
	{
		for (i = 0; i < MaxS; i++)
		{
			ListOfRectangles[i][j] = (short int *)malloc(B * sizeof(short int));
		}
	}

	buildTree();

	// Release memory.

	for (j = 0; j < A; j++)
	{
		for (i = 0; i < MaxS; i++)
		{
			free(ListOfRectangles[i][j]);
		}
	}

	for (i = 0; i < MaxS; i++)
	{
		free(ListOfRectangles[i]);
	}

	free(ListOfRectangles);

	//	Output stats.

	OpFile << endl;
	OpFile << "Tile side length      = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << i + MinTileSideSize - 1 << "  ";
	}

	OpFile << endl << endl;

	OpFile << "NumMatchIdentity      = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchIdentity[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchReflectHoriz  = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchReflectHoriz[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchReflectVert   = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchReflectVert[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchRotate180     = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchRotate180[i] << "  ";
	}

	OpFile << endl;

	OpFile << "NumMatchless          = ";

	for (i = 1; i <= NumTreesBuilt; i++)
	{
		OpFile << NumMatchless[i] << "  ";
	}

	OpFile << endl << endl;

	OpFile << "Program complete" << endl;

	return 0;
}