#include <iostream>
#include <iomanip>
#include <vector>

typedef std::vector<std::vector<int>> DType;

DType CreateArray(int W, int H){
	DType vec(H);

	for (auto& o : vec){
		o.resize(W);
	}

	return vec;
}

bool Check(DType& D, int W, int H){
	bool F = false;
	int A = 0, B = 0;
	for (int i = 0; i < W - 1; i++){
		F = false;
		for (int j = 0; j < H; j++){
			A = D[j][i];
			B = D[j][i + 1];
			if ((A == 0) || (B == 0) || (A == B)){
				F = true;
				break;
			}
		}
		if (F == false) return false;
	}

	for (int j = 0; j < H-1; j++){
		F = false;
		for (int i = 0; i < W; i++){
			A = D[j][i];
			B = D[j+1][i];
			if ((A == 0) || (B == 0) || (A == B)){
				F = true;
				break;
			}
		}
		if (F == false) return false;
	}
	return true;
}

bool Solve(std::vector<DType>& R, DType& D,const int& W,const int& H,int depth){
	auto Dup = D;

	if ((depth * 2 - 2) != (W*H)){
		for (int i = 0; i < H; i++){
			for (int j = 0; j < W; j++){
				if (D[i][j] == 0){
					for (int k = 0; k < 2; k++){
						if (k == 0){
							if ((j != W - 1) && (D[i][j + 1]==0)){
								D[i][j] = depth;
								D[i][j + 1] = depth;
								if (Check(D, W, H) == true) Solve(R, D, W, H, depth + 1);
								D = Dup;
							}
						}
						else{
							if ((i != H - 1) && (D[i+1][j]==0)){
								D[i][j] = depth;
								D[i+1][j] = depth;
								if (Check(D, W, H) == true) Solve(R, D, W, H, depth + 1);
								D = Dup;
							}
						}
					}
					goto L;
				}
			}
		}
	L:;
		return true;
	}
	else{
		R.push_back(D);
	}

	return true;
}


std::vector<DType> Fire(int W, int H){
	std::vector<DType> vec;
	auto D = CreateArray(W, H);

	Solve(vec, D, W, H,1);

	return vec;
}

bool ShowTatami(std::vector<DType>& vec,int W,int H,int Width = 3){
	for (auto& ooo : vec){
		for (auto& oo : ooo){
			for (auto& o : oo){
				std::cout << std::setw(Width) << std::right<< o << ' ';
			}
			std::cout << std::endl;
		}
		std::cout << std::endl;
	}
	std::cout << "We find " << vec.size()<<" count! at "<<W<<'x'<<H<< std::endl;
	return true;
}

int main(){

	auto R = Fire(6, 5);
	ShowTatami(R,6,5,2);
	R = Fire(8, 5);
	ShowTatami(R,8,5,2);
	R = Fire(6, 6);
	ShowTatami(R,6,6,2);
	R = Fire(6, 7);
	ShowTatami(R,6,7,2);
	return 0;
}


/* tatami solver-2 * /
#include <stdio.h>
#include <stdlib.h>
int xsize, ysize, size, count, mode = 1;

int check(int board[]){
	int i, j, flg, n[2];
	for (i = 0; i < xsize - 1; i++){
		flg = 0;
		for (j = 0; j < ysize; j++){
			n[0] = board[i + j * xsize];
			n[1] = board[i + 1 + j * xsize];
			if ((n[0] == 0) || (n[1] == 0) || (n[0] == n[1])){
				flg = 1;
				break;
			}
		}
		if (flg == 0)
			return 0;
	}
	for (j = 0; j < ysize - 1; j++){
		flg = 0;
		for (i = 0; i < xsize; i++){
			n[0] = board[i + j * xsize];
			n[1] = board[i + xsize + j * xsize];
			if ((n[0] == 0) || (n[1] == 0) || (n[0] == n[1])){
				flg = 1;
				break;
			}
		}
		if (flg == 0)
			return 0;
	}
	return 1;
}

void output(int board[]){
	int i;
	for (i = 0; i < size; i++){
		printf("%3d", board[i]);
		if (i % xsize != xsize - 1)
			printf(" ");
		else
			printf("\n");
	}
	printf("\n");
	return;
}

void solve(int board[], int depth){
	if (depth * 2 - 2 != size){
		int *board2, i, j, k;
		board2 = (int *)malloc(sizeof(int)* size);
		for (i = 0; i < size; i++)
			board2[i] = board[i];
		for (i = 0; i < size; i++){
			if (board[i] == 0){
				for (j = 0; j < 2; j++){
					if (j == 0){
						if ((i % xsize != xsize - 1) && (board[i + 1] == 0)){
							board[i] = board[i + 1] = depth;
							if (check(board) == 1)
								solve(board, depth + 1);
							for (k = 0; k < size; k++)
								board[k] = board2[k];
						}
					}
					else{
						if ((i < size - xsize) && (board[i + xsize] == 0)){
							board[i] = board[i + xsize] = depth;
							if (check(board) == 1)
								solve(board, depth + 1);
							for (k = 0; k < size; k++)
								board[k] = board2[k];
						}
					}
				}
				break;
			}
		}
		free(board2);
		return;
	}
	else{
		if (mode == 1)
			output(board);
		count++;
	}
}

int main(int argc, char *argv[]){
	int *board, i;
	/*if(argc<3)
	return 0;
	xsize = atoi(argv[1]);
	ysize = atoi(argv[2]);
	if(argc>3)
	mode = atoi(argv[3]);* /
	xsize = 6; ysize = 5; mode = 1;
	size = xsize * ysize;
	board = (int *)malloc(sizeof(int)* size);
	for (i = 0; i < size; i++)
		board[i] = 0;
	solve(board, 1);
	printf("%d\n", count);
	free(board);
	return 0;
}
*/