A Simple Search for Total Weight of some patterns...

#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>

using namespace std;

typedef set<int> IntSet;

struct Coord
{
    Coord(int aX = 0, int aY = 0): x(aX), y(aY){;}
    int x, y;
};

struct Matrix
{
    Matrix(size_t aRow = 0, size_t aCol = 0)
    {
    	init(aRow, aCol);
    	featureCounter = featureWeight = 0;
    }

    Matrix(const Matrix& other)
    {
        init(other.row, other.col);
        memcpy(data, other.data, other.row*other.col);
        featureCounter = other.featureCounter;
        featureWeight = other.featureWeight;
    }

    Matrix& operator=(const Matrix& other)
    {
        uninit();
        init(other.row, other.col);
        memcpy(data, other.data, other.row*other.col);
        featureCounter = other.featureCounter;
        featureWeight = other.featureWeight;
    }

    ~Matrix()
    {
        uninit();
    }

    void uninit()
    {
        if (data)
        {
            delete[] data;
            data = NULL;
            row = col = 0;
        }
    }

    void init(size_t aRow, size_t aCol)
    {
        row = aRow;
        col = aCol;
        featureCounter = 0;
        featureWeight = 0;
        if (row > 0 && col > 0)
        {
			data = new char[row*col];
        }
        else
        {
        	data = NULL;
        }
        memset(data, 0, row*col);
    }

    bool nextCoord(Coord& coord)
    {
    	for (int r = 0; r < row; r ++)
    	{
			for (int c = 0; c < col; c ++)
			{
				if (element(c, r) == 0)
				{
					coord.x = c;
					coord.y = r;
					return true;
				}
			}
    	}
        return false;
    }

	char& element(int c, int r)
	{
		return data[r*col + c];
	}
    char& element(const Coord& coord)
    {
        return element(coord.x, coord.y);
    }

    char element(int c, int r) const
	{
		return data[r*col + c];
	}
    char element(const Coord& coord) const
    {
        return element(coord.x, coord.y);
    }

    void print()
    {
    	printf("*******************************\n");
    	for (int r = 0; r < row; r ++)
    	{
    		for (int c = 0; c < col; c ++)
    		{
    			char base = 'A';
    			if (element(c, r) > 26)
    			{
    				base = 'a';
    			}
    			printf("%c", element(c, r) + base);
    		}
    		cout << endl;
    	}
    	printf("featureCounter=%d, featureWeight=%d\n", featureCounter, featureWeight);
    	printf("*******************************\n");
    }

    char* data;
    size_t row, col;
    size_t featureCounter;
    size_t featureWeight;
};

struct Feature
{
    virtual bool evaluate(const Matrix& matrix, const Coord& coord) = 0;
    virtual void fillIn(Matrix& matrix, const Coord& coord) = 0;
    virtual int weight() = 0;
};

struct FeatureFirst : public Feature
{
    bool evaluate(const Matrix& matrix, const Coord& coord)
    {
        return coord.x + 1 < matrix.col && coord.y < matrix.row
        && matrix.element(coord.x+1, coord.y) == 0;
    }
    void fillIn(Matrix& matrix, const Coord& coord)
    {
        matrix.featureCounter ++;
        matrix.element(coord) = matrix.featureCounter;
        matrix.element(Coord(coord.x+1, coord.y)) = matrix.featureCounter;
        matrix.featureWeight += 1;
    }

    int weight()
    {
        return 1;
    }
};

struct FeatureSecond : public Feature
{
    bool evaluate(const Matrix& matrix, const Coord& coord)
    {
        return coord.x  < matrix.col && coord.y + 1 < matrix.row
        && matrix.element(coord.x, coord.y+1) == 0;;
    }
    void fillIn(Matrix& matrix, const Coord& coord)
    {
        matrix.featureCounter ++;
        matrix.element(coord) = matrix.featureCounter;
        matrix.element(coord.x, coord.y+1) = matrix.featureCounter;
        matrix.featureWeight += 1;
    }

    int weight()
    {
        return 1;
    }
};

struct FeatureThird : public Feature
{
    bool evaluate(const Matrix& matrix, const Coord& coord)
    {
        return coord.x + 2 < matrix.col && coord.y < matrix.row
        && matrix.element(coord.x+1, coord.y) == 0 && matrix.element(coord.x+2, coord.y) == 0;
    }
    void fillIn(Matrix& matrix, const Coord& coord)
    {
        matrix.featureCounter ++;
        matrix.element(coord) = matrix.featureCounter;
        matrix.element(coord.x+1, coord.y) = matrix.featureCounter;
        matrix.element(coord.x+2, coord.y) = matrix.featureCounter;
        matrix.featureWeight += 1;
    }
    int weight()
    {
        return 1;
    }
};

struct FeatureFourth : public Feature
{
    bool evaluate(const Matrix& matrix, const Coord& coord)
    {
        return coord.x  < matrix.col && coord.y + 2 < matrix.row
        && matrix.element(coord.x, coord.y+1) == 0 && matrix.element(coord.x, coord.y+2) == 0;
    }
    void fillIn(Matrix& matrix, const Coord& coord)
    {
        matrix.featureCounter ++;
        matrix.element(coord) = matrix.featureCounter;
        matrix.element(coord.x, coord.y+1) = matrix.featureCounter;
        matrix.element(coord.x, coord.y+2) = matrix.featureCounter;
        matrix.featureWeight += 1;
    }
    int weight()
    {
        return 1;
    }
};

FeatureFirst featureFirst;
FeatureSecond featureSecond;
FeatureThird featureThird;
FeatureFourth featureFourth;
const int FeatureCountMax = 4;
Feature* features[FeatureCountMax] = {&featureFirst, &featureSecond, &featureThird, &featureFourth};

int next(Matrix& matrix, IntSet& intSet)
{
	Coord coord;
	if (matrix.nextCoord(coord))
	{
		for (int j = 0; j < FeatureCountMax; j ++)
		{
			if (features[j]->evaluate(matrix, coord))
			{
				Matrix subMatrix(matrix);
				features[j]->fillIn(subMatrix, coord);
				next(subMatrix, intSet);
			}
		}
	}
	else
	{
		//matrix.print();
		intSet.insert(matrix.featureWeight);
		return 1;
	}
	return 0;
}

size_t factorial(size_t n)
{
	size_t result = 1;
	for (size_t i = 2; i <= n; i ++)
	{
		result *= i;
	}
	return result;
}

int featureSearch(int w, int h)
{
	Matrix matrix(w, h);
	IntSet intSet;
	next(matrix, intSet);

	for (IntSet::const_iterator it = intSet.begin(); it != intSet.end(); it ++)
	{
		printf("[%d]", *it);
	}
	size_t factor = w*h;
	printf("total number of random patterns: %d and percentage of predefined patterns: %f\%\n", factor, (double)intSet.size()/(double)factor);
	fflush(stdout);
    return 0;
}


int main()
{
    featureSearch(6, 6);
    return 0;
}