#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 30

int row[MAX_SIZE][MAX_SIZE];
int col[MAX_SIZE][MAX_SIZE];


#define ONBEKEND '?'
#define VOL      '*'
#define LEEG     '_'

char old_val[MAX_SIZE];
char new_val[MAX_SIZE];
bool full[MAX_SIZE];
bool empty[MAX_SIZE];
int modified;
int found;

void tryplace(int i, int size, int *numbers)
{
	int ie, ib;
	if (numbers[0] == 0)
	{
		bool can_place = true;
		int j;
		for (j = i; j < size; j++)
		{
			if (old_val[j] == VOL)
			{	can_place = false;
				break;
			}
			new_val[j] = LEEG;
		}
		if (can_place)
		{
			int j;
			for (j = 0; j < size; j++)
				if (new_val[j] == VOL)
					empty[j] = false;
				else
					full[j] = false;
			found++;
		}
		return;
	}
	
	ib = i == 0 ? i : i+1;
	ie = ib + numbers[0]-1;
	for (; ie < size; ib++, ie++)
	{
		bool can_place = true;
		int j;
		for (j = i; j < ib; j++)
			if (old_val[j] == VOL)
			{	can_place = false;
				break;
			}
		if (can_place)
		{
			int j;			
			for (j = ib; j <= ie; j++)
				if (old_val[j] == LEEG)
				{	can_place = false;
					break;
				}
				
			if (can_place)
			{
				int j;
				for (j = i; j < ib; j++)
					new_val[j] = LEEG;
				for (j = ib; j <= ie; j++)
					new_val[j] = VOL;
			
				tryplace(ie+1, size, numbers + 1);
			}
		}
	}
}

int solve(char *rowcol, int nr, char* board, int pos, int off, int size, int *numbers)
{
	int i;
	int mod;
	for (i = 0; i < size; i++)
	{	old_val[i] = board[pos + off * i];
		full[i] = true;
		empty[i] = true;
	}
	
	found = 0;
	tryplace(0, size, numbers);
	
	if (found == 0)
        return 0;
	
	
	mod = 0;
	for (i = 0; i < size; i++)
	{	if (   full[i] && !empty[i]
			&& board[pos + off * i] == ONBEKEND)
		{	board[pos + off * i] = VOL;
			modified++;
			mod++;
		}
		if (   !full[i] && empty[i]
			&& board[pos + off * i] == ONBEKEND)
		{	board[pos + off * i] = LEEG;
			modified++;
			mod++;
		}
	}
	
#ifdef SHOW_SOLVING		
	if (mod)
	{	
		printf("%s %2d: ", rowcol, nr);
		for (int j = 0; j < size; j++)
			printf("%c", old_val[j]);
		printf(" -> ");
		for (int j = 0; j < size; j++)
			printf("%c", board[pos + off * j]);
		printf(" %d (%d)\n", mod, found);
	}
#endif

    return 1;
}

int solutions;
bool did_guess;

void solve_logic(int n, int m, char *board)
{
    do
	{
        bool possible = true;
		modified = 0;
		
		for (int i = 0; i < n; i++)
            if (!solve("row", i+1, board, i, n, m, row[i]))
                possible = false;
		for (int j = 0; j < m; j++)
            if (!solve("col", j+1, board, j*n, 1, n, col[j]))
                possible = false;

        if (!possible)
            return;

#ifdef SHOW_SOLVING		
		printf("\nmodified = %d\n", modified);
#endif
	}
	while (modified > 0);

    {
        int i, j, fi, fj;
        bool solved = true;

        for (i = 0; i < n && solved; i++)
            for (j = 0; j < m && solved; j++)
                if (board[i+j*n] == ONBEKEND)
                {
                    solved = false;
                    fi = i;
                    fj = j;
                }

        if (solved)
        {
        	solutions++;
#ifdef SHOW_SOLVING
            printf("--------------------\n");
            for (i = 0; i < n; i++)
            {
                int j;
                for (j = 0; j < m; j++)
                    printf("%c", board[i+j*n]);
                printf("\n");
            }
            printf("--------------------\n");
#endif
        }
        else
        {
        	did_guess = true;
        	
            char new_board[MAX_SIZE];

            for (i = 0; i < MAX_SIZE; i++)
                new_board[i] = board[i];

#ifdef SHOW_SOLVING
            printf("try %d,%d vol\n", fi, fj);
#endif
            new_board[fi+fj*n] = VOL;
            solve_logic(n, m, new_board);

            for (i = 0; i < MAX_SIZE; i++)
                new_board[i] = board[i];

#ifdef SHOW_SOLVING
            printf("try %d,%d leeg\n", fi, fj);    
#endif
            new_board[fi+fj*n] = LEEG;
            solve_logic(n, m, new_board);

#ifdef SHOW_SOLVING
            printf("backtrack %d,%d\n", fi, fj);
#endif
        }
    }
}


int compare(int n, int m, int *veld, int s, int i_f, int j_f)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
		{
			int xp = i + j*n;
			int yp = s + i*i_f + j*j_f;
			if (yp < 0 || yp >= n*m)
			{
				printf("error: n=%d, m=%d, %d + %d * %d + %d * %d = %d\n",
					n, m, s, i, i_f, j, j_f, yp);
				exit(0);
			}
			int x = veld[xp];
			int y = veld[yp];
			//printf("  compare %d %d\n", x, y);
			if (x < y)
				return -1;
			if (y < x)
				return 1;
		}
	return 0;
}

long total_nonograms;
long reducable_nonograms;
long hard_nonograms;
long single_sol_nonograms;
long error_nonograms;

void investigate(int n, int m, int *veld)
{
	int axes = 4;
	int nr = 1;
	int c;
	
	c = compare(n, m, veld, n-1, -1, n);
	if (c < 0)
	{	//printf("- smaller 1\n");
		return;
	}
	if (c == 0)
		nr++;

	c = compare(n, m, veld, n*(m-1), 1, -n);
	if (c < 0)
	{	//printf("- smaller 2\n");
		return;
	}
	if (c == 0)
		nr++;

	c = compare(n, m, veld, n*m-1, -1, -n);
	if (c < 0)
	{	//printf("- smaller 3\n");
		return;
	}
	if (c == 0)
		nr++;
		
	if (n == m)
	{
		axes += 4;
		
		c = compare(n, n, veld, 0, n, 1);
		if (c < 0)
		{	//printf("- smaller 4\n");
			return;
		}
		if (c == 0)
			nr++;
	
		c = compare(n, n, veld, n-1, n, -1);
		if (c < 0)
		{	//printf("- smaller 5\n");
			return;
		}
		if (c == 0)
			nr++;
	
		c = compare(n, n, veld, n*(n-1), -n, 1);
		if (c < 0)
		{	//printf("- smaller 6\n");
			return;
		}
		if (c == 0)
			nr++;
	
		c = compare(n, n, veld, n*n-1, -n, -1);
		if (c < 0)
		{	//printf("- smaller 7\n");
			return;
		}
		if (c == 0)
			nr++;
	}
	
	
	nr = axes / nr;
	total_nonograms += nr;
	
	// construct nonogram codes
	
	for (int i = 0; i < n; i++)
	{
		int len = 0;
		int k = 0;
		
		for (int j = 0; j < m; j++)
		{
			if (veld[i + j*n] == 0)
			{
				if (len > 0)
				{	
					row[i][k++] = len;
					len = 0;
				}
			}
			else
			{
				len++;
			}
		}
		if (len > 0)
		{	
			row[i][k++] = len;
		}
		row[i][k] = 0;
	}
	
	// first and last row may not be empty
	if (row[0][0] == 0)
	{
		reducable_nonograms += nr;
		return;
	}
	if (row[n-1][0] == 0)
	{
		reducable_nonograms += nr;
		return;
	}
	// may not have more than one adjecent empty row in the middle
	bool prev_empty = false;
	for (int i = 0; i < n; i++)
		if (row[i][0] == 0)
		{
			if (prev_empty)
			{
				reducable_nonograms += nr;
				return;
			}
			prev_empty = true;
		}
		else
			prev_empty = false;
	
	for (int j = 0; j < m; j++)
	{
		int len = 0;
		int k = 0;
		
		for (int i = 0; i < n; i++)
		{
			if (veld[i + j*n] == 0)
			{
				if (len > 0)
				{	
					col[j][k++] = len;
					len = 0;
				}
			}
			else
			{
				len++;
			}
		}
		if (len > 0)
		{	
			col[j][k++] = len;
		}
		col[j][k] = 0;
	}

	// first and last col may not be empty
	if (col[0][0] == 0)
	{
		reducable_nonograms += nr;
		return;
	}
	if (col[m-1][0] == 0)
	{
		reducable_nonograms += nr;
		return;
	}

	// may not have more than one adjecent empty col in the middle
	prev_empty = false;
	for (int j = 0; j < m; j++)
		if (col[j][0] == 0)
		{
			if (prev_empty)
			{
				reducable_nonograms += nr;
				return;
			}
			prev_empty = true;
		}
		else
			prev_empty = false;

#if 0
	printf("Investigate (%d):\n", nr);
	for (int i = 0; i < n; i++)
	{	
		for (int j = 0; j < m; j++)
			printf(" %d", veld[i + j*n]);
		printf("\n");
	}
	for (int i = 0; i < n; i++)
	{
		printf("row %d: ", i+1);
		for (int k = 0; row[i][k] > 0; k++)
			printf(" %d", row[i][k]);
		printf("\n");
	}
	for (int j = 0; j < m; j++)
	{
		printf("col %d: ", j+1);
		for (int k = 0; col[j][k] > 0; k++)
			printf(" %d", col[j][k]);
		printf("\n");
	}
	printf("\n");
#endif

	char board[MAX_SIZE];
	for (int i = 0; i < MAX_SIZE; i++)
		board[i] = ONBEKEND;

	solutions = 0;
	did_guess = false;	
    solve_logic(n, m, board);
	
	if (solutions == 0)
		error_nonograms++; //printf("Error: No solutions found\n");
	else if (solutions == 1 && did_guess)
	{
		hard_nonograms += nr;
#ifdef PRINT_SOLUTIONS	
		printf("FOUND!!!: one solution, needing guessing\n");
		for (int i = 0; i < n; i++)
		{	
			for (int j = 0; j < m; j++)
				printf(" %d", veld[i + j*n]);
			printf("\n");
		}
		for (int i = 0; i < n; i++)
		{
			printf("row %d: ", i+1);
			for (int k = 0; row[i][k] > 0; k++)
				printf(" %d", row[i][k]);
			printf("\n");
		}
		for (int j = 0; j < m; j++)
		{
			printf("col %d: ", j+1);
			for (int k = 0; col[j][k] > 0; k++)
				printf(" %d", col[j][k]);
			printf("\n");
		}
		printf("\n");
#endif
	}
	else if (solutions == 1)
		single_sol_nonograms += nr; //printf("One solution\n");
	else
		; //printf("There are %d solutions\n", solutions);
}

void investigate(int n, int m)
{
	//printf("Investigate %d, %d\n", n, m);
		
	int veld[MAX_SIZE];
	int nm = n * m;
	if (nm >= MAX_SIZE)
	{
		printf("n * m = %d is too high\n", nm);
		return;
	}
	
	for (int i = 0; i < nm; i++)
		veld[i] = 0;

	long total = 1 << nm;	
	total_nonograms = 0;
	reducable_nonograms = 0;
	hard_nonograms = 0;
	single_sol_nonograms = 0;
	error_nonograms = 0;
	for (int k = 0; k < total; k++)
	{
		investigate(n, m, veld);
		
		// next
		for (int j = nm-1; j >= 0; j--)
			if (veld[j] == 0)
			{
				veld[j] = 1;
				break;
			}
			else
				veld[j] = 0;
	}
	
	fprintf(stderr, "%2d %2d: ", n, m);
	if (total != total_nonograms)
	{
		fprintf(stderr, "Error: total  %d %d\n", total, total_nonograms);
	}
	else if (error_nonograms > 0)
	{
		fprintf(stderr, "Error: error nonograms\n");
	}
	else
	{
		fprintf(stderr, "%8d %8d %8d %8d %8d\n", 
			total_nonograms,
			reducable_nonograms,
			hard_nonograms,
			single_sol_nonograms,
			total_nonograms - reducable_nonograms - hard_nonograms - single_sol_nonograms);
	}
	
}

int main(int argc, char *argv[])
{
	for (int nm = 4; nm < MAX_SIZE; nm++)
		for (int n = 2; n < MAX_SIZE; n++)
			for (int m = n; m < MAX_SIZE && n*m <= nm; m++)
				if (n*m == nm)
					investigate(n,m);
	printf("\n\ndone\n");
	return 0;
}