#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstdint>

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


DType Normalize(DType vec){
	std::map<NType, NType> m;
	NType n = 1;

	for (auto& oo : vec){
		for (auto& o : oo){
			if (m[o] == 0)m[o] = n++;
			o = m[o];
		}
	}

	return vec;
}

bool ShowTatamiOne(DType& vec){
	std::map<NType, NType> m;
	NType n = 1;

	m[0] = -1;

	for (auto& oo : vec){
		for (auto& o : oo){
			if (m[o] == 0)m[o] = n++;
//			std::cout << m[o] << ',';
			std::cout << o << ',';
			
		}
		std::cout << std::endl;
	}

	return true;
}

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

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

	return vec;
}

bool IsFull(DType& vec){
	for (auto& oo : vec){
		for (auto& o : oo){
			if (o == 0){
				return false;
			}
		}
	}
	return true;
}
bool IsValid(DType& vec){
	//empty
	return true;//わかんなーい。
}

bool Paint(DType& d, int x, int y,volatile NType & N, bool IsRight,bool IsForce=false){
	N++;
	if (d.size() <= y)return false;	
	if (d[y].size() <= x)return false;
	if (IsRight == true){
		if (d[y].size() <= x + 1)return false;
		if (IsForce == false){
			if ((d[y][x] != 0 || d[y][x + 1] != 0)) return false;
		}
		d[y][x] = N;
		d[y][x+1] = N;
	}
	else{
		if (d.size() <= y + 1)return false;
		if (IsForce == false){
			if (d[y][x] != 0 || d[y + 1][x] != 0) return false;
		}
		d[y][x] = N;
		d[y+1][x] = N;
	}
	
	return true;

}

bool Compair(DType& x, DType& y){

	if (x.size() != y.size()) return false;
	auto A = Normalize(x);
	auto B = Normalize(y);

	for (std::size_t i = 0; i < A.size(); i++){
		if (A[i].size() != B[i].size()) return false;
		for (std::size_t j = 0; j < A[i].size(); j++){
			if (A[i][j] != B[i][j]) return false;
		}
	}

	return true;
}

bool HogeRec(std::vector<DType>& R, DType& D, int x, int y,NType& N, bool IsRight = true){
	DType& Dup = D;

	if (Dup.size() <= y)return false;	
	if (Dup[y].size() <= x)return false;
	
	bool F = Paint(Dup, x, y, N, IsRight);
	if (F == false)return false;

	HogeRec(R, Dup, x + 1, y, N);
	HogeRec(R, Dup, x + 1, y, N, false);
	HogeRec(R, Dup, x, y + 1, N);
	HogeRec(R, Dup, x, y + 1, N, false);
	/* */
	if (IsFull(Dup) == true){
		if (IsValid(Dup) == true){
			R.push_back(Dup);
			return true;
		}
	}
	return true;
}

std::vector<DType> MakeHoge(int W, int H){
	std::vector<DType> vec;
	DType d;
	NType N = 1000;//畳の色。表示時に正規化するんで、適当な数字で開始。小さすぎると正規化失敗する。Orz

	for (int i = 0; i < H; i++){
		for (int j = 0; j < W; j++){
			d = CreateMass(W, H);
			HogeRec(vec, d, i, j, N, true);
			d = CreateMass(W, H);
			HogeRec(vec, d, i, j, N, false);
		}
	}

	
	for (std::size_t i = 0; i < vec.size(); i++){
		for (std::size_t j = 0; j < vec.size(); j++){
			if (i == j) continue;
			if (Compair(vec[i], vec[j]) == true ){
				vec.erase(vec.begin() + j);
				i--;
				break;
			}
		}
	}

	return vec;
}

bool ShowTatami(std::vector<DType>& vec){

	for (auto& ooo : vec){
		ShowTatamiOne(ooo);
		std::cout << std::endl;
	}

	return true;
}

int main(){

	auto R = MakeHoge(5, 6);
	ShowTatami(R);
	
	return true;
}