fork download 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <tuple>
  5. #include <algorithm>
  6.  
  7. //小文字大文字は判別する。
  8. //処理速度度返し！！Orz
  9.  
  10. typedef std::vector<std::tuple<int, int, std::string>> RType;
  11.  
  12.  
  13. RType FindRight(const std::vector<std::string>& Vec, const std::string& Word, bool IsRev = false){
  14. 	std::size_t Cur = 0;
  15. 	std::size_t x = 0, y = 0;
  16. 	RType Ret;
  17.  
  18. 	for (std::size_t i = 0; i < Vec.size(); i++){
  19. 		for (std::size_t j = 0; j < Vec[i].size(); j++){
  20. 			if (Vec[i][j] == Word[Cur]){
  21. 				if (Cur == 0){
  22. 					x = j;
  23. 					y = i;
  24. 				}
  25. 				Cur++;
  26. 			}
  27. 			else{
  28. 				if (Cur != 0) j--;
  29. 				Cur = 0;
  30. 			}
  31. 			if (Cur == Word.size()){
  32. 				if (IsRev == false){
  33. 					Ret.push_back(std::make_tuple(y, x, "R"));
  34. 				}
  35. 				else{
  36. 					Ret.push_back(std::make_tuple(i, j, "L"));
  37. 				}
  38. 				//return Ret;//一個見つけたらやめる
  39. 			}
  40. 		}
  41. 		Cur = 0;
  42. 	}
  43.  
  44. 	return Ret;
  45. }
  46. RType FindBottom(const std::vector<std::string>& Vec,const std::string& Word,bool IsRev =false){
  47. 	std::size_t Cur = 0;
  48. 	std::size_t x = 0, y = 0;
  49. 	std::size_t j = 0;
  50. 	RType Ret;
  51. 	std::size_t M = 0;
  52. 	while (true){
  53. 		for (std::size_t i = 0; i < Vec.size(); i++){
  54. 			if (Vec[i].size() < j) continue;
  55. 			M = std::max(M, Vec[i].size());
  56. 			if (Vec[i][j] == Word[Cur]){
  57. 				if (Cur == 0){
  58. 					x = j;
  59. 					y = i;
  60. 				}
  61. 				Cur++;
  62. 			}
  63. 			else{
  64. 				if (Cur != 0) i--;
  65. 				Cur = 0;
  66. 			}
  67. 			if (Cur == Word.size()){
  68. 				if (IsRev == false){
  69. 					Ret.push_back(std::make_tuple(y, x, "D"));
  70. 				}
  71. 				else{
  72. 					Ret.push_back(std::make_tuple(i, j, "U"));
  73. 				}
  74. 				//return Ret;//一個見つけたらやめる
  75. 			}
  76.  
  77. 		}
  78. 		Cur = 0;
  79. 		j++;
  80. 		if (j >= M) break;
  81. 	}
  82.  
  83. 	return Ret;
  84. }
  85. RType FindNanameMae(std::vector<std::string>& Vec, std::string Word,bool IsRev = false){
  86. 	std::size_t vs = Vec.size();
  87. 	std::size_t ss = Word.size();
  88. 	std::size_t Cur = 0;
  89. 	std::size_t x = 0, y = 0;
  90. 	bool F = false;
  91. 	RType Ret;
  92. 	std::vector < std::pair<int, int>> T;
  93. 	int A = 0, B = 0;
  94.  
  95. 	for (std::size_t i = 0; i < Vec.size(); i++){
  96. 		for (std::size_t j = 0; j < Vec[i].size(); j++){
  97. 			for (std::size_t k = 0; k + i < Vec.size() && k + j < Vec[i + k].size(); k++){
  98. 				if (Vec[i + k][j + k] == Word[Cur]){
  99. 					if (Cur == 0){
  100. 						x = j+k;
  101. 						y = i+k;
  102. 					}
  103. 					Cur++;
  104. 				}
  105. 				else{
  106. 					Cur = 0;
  107. 				}
  108. 				if (Cur == Word.size()){
  109.  
  110. 					if (IsRev == false){
  111. 						A = y;
  112. 						B = x;
  113. 					}
  114. 					else{
  115. 						A = i+k;
  116. 						B = j+k;
  117. 					}
  118. 					auto P = std::make_pair(A, B);
  119. 					for (auto& o : T){
  120. 						F = o == P;
  121. 						if (F == true) break;
  122. 					}
  123. 					if (F == true)continue;
  124.  
  125. 					if (IsRev == false){
  126. 						T.push_back(std::make_pair(y, x));
  127. 						Ret.push_back(std::make_tuple(y, x, "NM"));
  128. 					}
  129. 					else{
  130. 						T.push_back(std::make_pair(i+k, j+k));
  131. 						Ret.push_back(std::make_tuple(i+k, j+k, "NMR"));
  132. 					}
  133. 					//return Ret;//一個見つけたらやめる
  134. 				}
  135. 			}
  136. 			Cur = 0;
  137. 		}
  138. 	}
  139. 	return Ret;
  140. }
  141. RType FindNanameUsiro(std::vector<std::string>& Vec, std::string Word,bool IsRev = false){
  142. 	std::size_t vs = Vec.size();
  143. 	std::size_t ss = Word.size();
  144. 	std::size_t Cur = 0;
  145. 	std::size_t x = 0, y = 0;
  146. 	bool F = false;
  147. 	RType Ret;
  148. 	std::vector < std::pair<int, int>> T;
  149. 	int A = 0, B = 0;
  150.  
  151. 	for (std::size_t i = 0; i < Vec.size(); i++){
  152. 		for (int j = 0; j < Vec[i].size(); j++){
  153. 			for (int k = 0; k + i < Vec.size() && j-k >= 0; k++){
  154. 				if (Vec[i + k][j - k] == Word[Cur]){
  155. 					if (Cur == 0){
  156. 						x = j+k;
  157. 						y = i+k;
  158. 					}
  159. 					Cur++;
  160. 				}
  161. 				else{
  162. 					Cur = 0;
  163. 				}
  164. 				if (Cur == Word.size()){
  165.  
  166. 					if (IsRev == false){
  167. 						A = y;
  168. 						B = x;
  169. 					}
  170. 					else{
  171. 						A = i+k;
  172. 						B = j-k;
  173. 					}
  174. 					auto P = std::make_pair(A, B);
  175. 					for (auto& o : T){
  176. 						F = o == P;
  177. 						if (F == true) break;
  178. 					}
  179. 					if (F == true)continue;
  180.  
  181. 					if (IsRev == false){
  182. 						T.push_back(std::make_pair(y, x));
  183. 						Ret.push_back(std::make_tuple(y, x, "NU"));
  184. 					}
  185. 					else{
  186. 						T.push_back(std::make_pair(i+k, j-k));
  187. 						Ret.push_back(std::make_tuple(i+k, j-k, "NUR"));
  188. 					}
  189. 					//return Ret;//一個見つけたらやめる
  190. 				}
  191. 			}
  192. 			Cur = 0;
  193. 		}
  194. 	}
  195. 	return Ret;
  196. }
  197.  
  198. RType FindWord(std::vector<std::string>& Vec,const std::string& Word){
  199. 	RType Ret;
  200. 	auto bs = std::back_inserter(Ret);
  201.  
  202.  
  203. 	/* */
  204. 	auto FR = FindRight(Vec, Word);
  205. 	for (auto& o : FR)bs = o;
  206. 	/* */
  207. 	auto FB = FindBottom(Vec, Word);
  208. 	for (auto& o : FB)bs = o;
  209. 	/* */
  210. 	auto FNM = FindNanameMae(Vec, Word);
  211. 	for (auto& o : FNM)bs = o;
  212. 	/* */
  213. 	auto FNU = FindNanameUsiro(Vec, Word);
  214. 	for (auto& o : FNU)bs = o;
  215. 	/* */
  216. 	std::string T(Word.rbegin(),Word.rend());
  217.  
  218. 	/* */
  219. 	auto FRR = FindRight(Vec, T, true);
  220. 	for (auto& o : FRR)bs = o;
  221. 	/* */
  222. 	auto FBR = FindBottom(Vec, T,true);
  223. 	for (auto& o : FBR)bs = o;
  224. 	/* */
  225. 	auto FNMR = FindNanameMae(Vec, T,true);
  226. 	for (auto& o : FNMR)bs = o;
  227. 	/* */
  228. 	auto FNUR = FindNanameUsiro(Vec, T,true);
  229. 	for (auto& o : FNUR)bs = o;
  230. 	/* */
  231. 	return Ret;
  232.  
  233. }
  234.  
  235.  
  236. int main(){
  237. 	std::vector<std::string> vec = {
  238. 		"WVERTICALL",
  239. 		"ROOAFFLSAB",
  240. 		"ACRILIATOA",
  241. 		"NDODKONWDC",
  242. 		"DRKESOODDK",
  243. 		"OEEPZEGLIW",
  244. 		"MSIIHOAERA",
  245. 		"ALRKRRIRER",
  246. 		"KODIDEDRCD",
  247. 		"HELWSLEUTH",
  248. 	};
  249. 	std::vector<std::string> Words = {
  250. 		"WEEK",
  251. 		"FIND",
  252. 		"RANDOM",
  253. 		"SLEUTH",
  254. 		"BACKWARD",
  255. 		"VERTICAL",
  256. 		"DIAGONAL",
  257. 		"WIKIPEDIA",
  258. 		"HORIZONTAL",
  259. 		"WORDSEARCH",
  260. 	};
  261. 	std::vector<std::string> vec2 = {
  262. 		"MAMEMAM",
  263. 		"AAoMoAA",
  264. 		"MoMAMoM",
  265. 		"EMAEAME",
  266. 		"MoMAMoM",
  267. 		"AAoMoAA",
  268. 		"MAMEMAM",
  269. 	};
  270.  
  271. 	std::string MAME = "MAME";
  272.  
  273. 	for (std::size_t i = 0; i < Words.size(); i++){
  274. 		auto R = FindWord(vec, Words[i]);
  275.  
  276. 		if (R.size() == 0){
  277. 			std::cout << Words[i] << " is NotFound!" << std::endl;
  278. 			continue;
  279. 		}
  280. 		std::cout << Words[i] << " is ";
  281. 		for (auto& o : R) std::cout << std::get<0>(o)+1 << ',' << std::get<1>(o)+1 << "@" << std::get<2>(o) << ' ';
  282. 		std::cout << std::endl;
  283. 	}
  284. 	auto R = FindWord(vec2, MAME);
  285.  
  286. 	if (R.size() == 0){
  287. 		std::cout << MAME << " is NotFound!" << std::endl;
  288. 	}
  289. 	std::cout << MAME << " is ";
  290. 	for (auto& o : R) std::cout << std::get<0>(o)+1 << ',' << std::get<1>(o)+1 << "@" << std::get<2>(o) << ' ';
  291. 	std::cout << std::endl;
  292.  
  293. 	return 0;
  294. }
Success #stdin #stdout 0s 3488KB
comments (?)
stdin 
Standard input is empty
stdout 
WEEK is NotFound!
FIND is 2,5@NM 
RANDOM is 2,1@D 
SLEUTH is 10,5@R 
BACKWARD is 2,10@D 
VERTICAL is 1,2@R 
DIAGONAL is 9,7@U 
WIKIPEDIA is 10,4@U 
HORIZONTAL is 10,1@NUR 
WORDSEARCH is 1,1@NM 
MAME is 1,1@R 7,1@R 1,1@D 1,7@D 1,1@NM 1,7@NU 1,7@L 7,7@L 7,1@U 7,7@U 7,7@NMR 7,1@NUR
https://ideone.com/nBl1Uv
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!