[백준/BOJ] 백준 20166번 : 문자열 지옥에 빠진 호석

https://www.acmicpc.net/problem/20166

20166번: 문자열 지옥에 빠진 호석

각각의 위치에서 시작해서 만들어지는 문자열을 map<string, int> result에 문자열과 문자열이 만들어지는 횟수도 세어가며 저장을 해서 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
using namespace std;

int n, m, k;
vector<string> board;
vector<string> like;
map<string, int> result;
int dxdy[8][2] = { {0,-1},{-1,0},{0,1},{1,0},{-1,-1},{-1,1},{1,1},{1,-1} };

void Solve(pair<int, int> here, string maked)
{
	maked += board[here.first][here.second];

	if (maked.size() > 5)
		return;

	if (result.count(maked) == 0)
		result.insert(make_pair(maked, 1));
	else
		result[maked]++;

	for (int dir = 0; dir < 8; dir++)
	{
		pair<int, int> there = make_pair(here.first + dxdy[dir][0], here.second + dxdy[dir][1]);

		if (there.first < 0)
			there.first = n - 1;
		if (there.first >= n)
			there.first = 0;
		if (there.second < 0)
			there.second = m - 1;
		if (there.second >= m)
			there.second = 0;

		Solve(there, maked);
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++)
	{
		string input;
		cin >> input;

		board.push_back(input);
	}

	for (int i = 0; i < k; i++)
	{
		string input;
		cin >> input;

		like.push_back(input);
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			pair<int, int> start = make_pair(i, j);
			string maked = "";

			Solve(start, maked);
		}
	}

	for (int i = 0; i < like.size(); i++)
	{
		if (result.count(like[i]) == 0)
			cout << 0 << "\n";

		else
			cout << result[like[i]] << "\n";
	}

	return 0;
}