[백준 20166] 문자열 지옥에 빠진 호석 (C++)

이 문제는 격자에서 상하좌우 및 대각선으로 이동해가며, 신이 좋아하는 문자열의 갯수를 얼마나 만들 수 있는지 확인하는 문제이다.

따라서, bfs로 여러 칸들을 중복을 허용하여 방문해가며 문자열을 만들어야 한다.

그리고, 미리 만들 수 있는 모든 경우의 문자열에 대한 경우의 수를 구해놓은 뒤, 신이 좋아하는 문자열이 주어질 때 마다 곧바로 출력하는 쪽이 연산을 줄일 수 있다.

따라서, bfs로 i행 j열에서 시작해서 신이 좋아하는 문자열의 최대 길이인 5보다 작거나 같을 때까지 중복을 허용해 방문해가며 만들어진 문자열을 unordered_map을 통해 경우의 수를 세어주면 된다.

#include <bits/stdc++.h>
using namespace std;

int n, m, k;
string grid[1000];
unordered_map<string, int> um;
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

void bfs(int i, int j) {
	queue<tuple<int, int, string>> q;
	string init;
	init += grid[i][j];
	um[init]++;
	q.push({i, j, init});

	while (!q.empty()) {
		int x, y;
		string s;
		tie(x, y, s) = q.front();
		q.pop();

		for (int dir = 0; dir < 8; dir++) {
			int nx = x + dx[dir], ny = y + dy[dir];

			if (nx < 0) nx += n;
			else if (nx >= n) nx -= n;
			if (ny < 0) ny += m;
			else if (ny >= m) ny -= m;

			string ns = s + grid[nx][ny];
			um[ns]++;
			if (ns.length() < 5) q.push({nx, ny, ns});
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;
	for (int i = 0; i < n; i++) cin >> grid[i];

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) bfs(i, j);
	}
	
	for (int i = 0; i < k; i++) {
		string favorite;
		cin >> favorite;
		cout << um[favorite] << "\n";
	}
}