#include <iostream>
#include <string>
#include <vector>
#include <tuple>

typedef std::vector<std::tuple<int, int, std::string>> DType;

DType FindWord(const std::vector<std::string>& Vec, std::string Word){
	DType Dir = {
		std::make_tuple(-1,  1, "LD"),	std::make_tuple(0,  1, "D"),std::make_tuple(1,  1, "RD"),
		std::make_tuple(-1,  0, "L"),								std::make_tuple(1,  0, "R"),
		std::make_tuple(-1, -1, "LU"),	std::make_tuple(0, -1, "U"),std::make_tuple(1, -1, "RU"),
	};
	DType Ret;
	int px = 0;
	int py = 0;
	int Cur = 0;

	for (int i = 0; i < Vec.size(); i++){
		for (int j = 0; j < Vec[i].size(); j++){
			for (auto& o : Dir){
				for (std::size_t k = 0; k < Word.size(); k++){
					px = j + std::get<0>(o)*k;
					py = i + std::get<1>(o)*k;
					if (py < 0)break;
					if (py >= Vec.size()) break;
					if (px < 0)break;
					if (px >= Vec[py].size())break;

					if (Vec[py][px] == Word[Cur]){
						Cur++;
					}
					else{
						Cur = 0;
					}

				}
				if (Cur == Word.size()){
					Ret.push_back(std::make_tuple(i, j, std::get<2>(o)));
				}
				Cur = 0;
			}
		}
	}

	return Ret;
}


int main(){
	std::vector<std::string> vec = {
		"WVERTICALL",
		"ROOAFFLSAB",
		"ACRILIATOA",
		"NDODKONWDC",
		"DRKESOODDK",
		"OEEPZEGLIW",
		"MSIIHOAERA",
		"ALRKRRIRER",
		"KODIDEDRCD",
		"HELWSLEUTH",
	};
	std::vector<std::string> Words = {
		"WEEK",
		"FIND",
		"RANDOM",
		"SLEUTH",
		"BACKWARD",
		"VERTICAL",
		"DIAGONAL",
		"WIKIPEDIA",
		"HORIZONTAL",
		"WORDSEARCH",
	};
	std::vector<std::string> vec2 = {
		"MAMEMAM",
		"AAoMoAA",
		"MoMAMoM",
		"EMAEAME",
		"MoMAMoM",
		"AAoMoAA",
		"MAMEMAM",
	};

	std::string MAME = "MAME";

	for (std::size_t i = 0; i < Words.size(); i++){
		auto R = FindWord(vec, Words[i]);

		if (R.size() == 0){
			std::cout << Words[i] << " is NotFound!" << std::endl;
			continue;
		}
		std::cout << Words[i] << " is ";
		for (auto& o : R) std::cout << std::get<0>(o)+1 << ',' << std::get<1>(o)+1 << "@" << std::get<2>(o) << ' ';
		std::cout << std::endl;
	}
	auto R = FindWord(vec2, MAME);

	if (R.size() == 0){
		std::cout << MAME << " is NotFound!" << std::endl;
	}
	std::cout << MAME << " is ";
	for (auto& o : R) std::cout << std::get<0>(o)+1 << ',' << std::get<1>(o)+1 << "@" << std::get<2>(o) << ' ';
	std::cout << std::endl;

	return 0;
}