[백준 20166] 문자열 지옥에 빠진 호석

문제

www.acmicpc.net/problem/20166

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

 

풀이

1. 문제에서 친절하게 찾고자하는 문자열이 중복되는 경우가 존재할 수 있다고 했으므로 맵을 사용해서 한 번 계산한 문자열은 다시 계산하지 않을 수 있습니다.

 

2. 문자열을 찾는 쿼리마다 n * m 격자를 순회하는데 이 때 아래와 같이 맵밖으로 나가는 경우만 따로 처리해주면 "현재 좌표에서부터 찾을 수있는 문자열의 개수"를 반환하는 함수를 작성해 해결할 수 있습니다.

 

 

코드

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

const int dir[8][2] = { {-1,0},{1,0},{0,-1},{0,1},{1,1},{-1,-1},{-1,1},{1,-1} };
int n, m, k, l, nr, nc, cnt;
string s;
char g[11][11];
map<string, int> mp;

int go(int r, int c, int idx) {
	if (idx == l - 1) return 1;
	int ret = 0;
	for (int i = 0; i < 8; i++) {
		nr = r + dir[i][0], nc = c + dir[i][1];
        if (nr < 0) nr += n;
        if (nc < 0) nc += m;
        if (nr >= n) nr -= n;
        if (nc >= m) nc -= m;
		if (g[nr][nc] == s[idx + 1]) ret += go(nr, nc, idx + 1);
	}
	return ret;
}

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

	cin >> n >> m >> k;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> g[i][j];
	for (int i = 0; i < k; i++) {
		cin >> s;
		if (!mp[s]) {
			l = s.length(), cnt = 0;
			for (int j = 0; j < n; j++) 
				for (int k = 0; k < m; k++) 
					if (g[j][k] == s[0]) 
						cnt += go(j, k, 0);
			mp[s] = cnt;
		}
		cout << mp[s] << '\n';
	}
}