fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. #include <cstdint>
  6.  
  7. typedef int NType;
  8. typedef std::vector<std::vector<NType>> DType;
  9.  
  10.  
  11. DType Normalize(DType vec){
  12. 	std::map<NType, NType> m;
  13. 	NType n = 1;
  14.  
  15. 	for (auto& oo : vec){
  16. 		for (auto& o : oo){
  17. 			if (m[o] == 0)m[o] = n++;
  18. 			o = m[o];
  19. 		}
  20. 	}
  21.  
  22. 	return vec;
  23. }
  24.  
  25. bool ShowTatamiOne(DType& vec){
  26. 	std::map<NType, NType> m;
  27. 	NType n = 1;
  28.  
  29. 	m[0] = -1;
  30.  
  31. 	for (auto& oo : vec){
  32. 		for (auto& o : oo){
  33. 			if (m[o] == 0)m[o] = n++;
  34. //			std::cout << m[o] << ',';
  35. 			std::cout << o << ',';
  36.  
  37. 		}
  38. 		std::cout << std::endl;
  39. 	}
  40.  
  41. 	return true;
  42. }
  43.  
  44. DType CreateMass(int W, int H){
  45. 	DType vec(H);
  46.  
  47. 	for (auto& o : vec)o.resize(W);
  48.  
  49. 	return vec;
  50. }
  51.  
  52. bool IsFull(DType& vec){
  53. 	for (auto& oo : vec){
  54. 		for (auto& o : oo){
  55. 			if (o == 0){
  56. 				return false;
  57. 			}
  58. 		}
  59. 	}
  60. 	return true;
  61. }
  62. bool IsValid(DType& vec){
  63. 	//empty
  64. 	return true;//わかんなーい。
  65. }
  66.  
  67. bool Paint(DType& d, int x, int y,volatile NType & N, bool IsRight,bool IsForce=false){
  68. 	N++;
  69. 	if (d.size() <= y)return false;	
  70. 	if (d[y].size() <= x)return false;
  71. 	if (IsRight == true){
  72. 		if (d[y].size() <= x + 1)return false;
  73. 		if (IsForce == false){
  74. 			if ((d[y][x] != 0 || d[y][x + 1] != 0)) return false;
  75. 		}
  76. 		d[y][x] = N;
  77. 		d[y][x+1] = N;
  78. 	}
  79. 	else{
  80. 		if (d.size() <= y + 1)return false;
  81. 		if (IsForce == false){
  82. 			if (d[y][x] != 0 || d[y + 1][x] != 0) return false;
  83. 		}
  84. 		d[y][x] = N;
  85. 		d[y+1][x] = N;
  86. 	}
  87.  
  88. 	return true;
  89.  
  90. }
  91.  
  92. bool Compair(DType& x, DType& y){
  93.  
  94. 	if (x.size() != y.size()) return false;
  95. 	auto A = Normalize(x);
  96. 	auto B = Normalize(y);
  97.  
  98. 	for (std::size_t i = 0; i < A.size(); i++){
  99. 		if (A[i].size() != B[i].size()) return false;
  100. 		for (std::size_t j = 0; j < A[i].size(); j++){
  101. 			if (A[i][j] != B[i][j]) return false;
  102. 		}
  103. 	}
  104.  
  105. 	return true;
  106. }
  107.  
  108. bool HogeRec(std::vector<DType>& R, DType& D, int x, int y,NType& N, bool IsRight = true){
  109. 	DType& Dup = D;
  110.  
  111. 	if (Dup.size() <= y)return false;	
  112. 	if (Dup[y].size() <= x)return false;
  113.  
  114. 	bool F = Paint(Dup, x, y, N, IsRight);
  115. 	if (F == false)return false;
  116.  
  117. 	HogeRec(R, Dup, x + 1, y, N);
  118. 	HogeRec(R, Dup, x + 1, y, N, false);
  119. 	HogeRec(R, Dup, x, y + 1, N);
  120. 	HogeRec(R, Dup, x, y + 1, N, false);
  121. 	/* */
  122. 	if (IsFull(Dup) == true){
  123. 		if (IsValid(Dup) == true){
  124. 			R.push_back(Dup);
  125. 			return true;
  126. 		}
  127. 	}
  128. 	return true;
  129. }
  130.  
  131. std::vector<DType> MakeHoge(int W, int H){
  132. 	std::vector<DType> vec;
  133. 	DType d;
  134. 	NType N = 1000;//畳の色。表示時に正規化するんで、適当な数字で開始。小さすぎると正規化失敗する。Orz
  135.  
  136. 	for (int i = 0; i < H; i++){
  137. 		for (int j = 0; j < W; j++){
  138. 			d = CreateMass(W, H);
  139. 			HogeRec(vec, d, i, j, N, true);
  140. 			d = CreateMass(W, H);
  141. 			HogeRec(vec, d, i, j, N, false);
  142. 		}
  143. 	}
  144.  
  145.  
  146. 	for (std::size_t i = 0; i < vec.size(); i++){
  147. 		for (std::size_t j = 0; j < vec.size(); j++){
  148. 			if (i == j) continue;
  149. 			if (Compair(vec[i], vec[j]) == true ){
  150. 				vec.erase(vec.begin() + j);
  151. 				i--;
  152. 				break;
  153. 			}
  154. 		}
  155. 	}
  156.  
  157. 	return vec;
  158. }
  159.  
  160. bool ShowTatami(std::vector<DType>& vec){
  161.  
  162. 	for (auto& ooo : vec){
  163. 		ShowTatamiOne(ooo);
  164. 		std::cout << std::endl;
  165. 	}
  166.  
  167. 	return true;
  168. }
  169.  
  170. int main(){
  171.  
  172. 	auto R = MakeHoge(5, 6);
  173. 	ShowTatami(R);
  174.  
  175. 	return true;
  176. }
Runtime error #stdin #stdout 0s 3480KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/IZDTEt
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!