[백준] 2186번 - 문자판 (C++) 문제 및 풀이

문졔) 백준 - 동적 계획법 (Dynamic Programming) - 문자판

-> https://www.acmicpc.net/problem/2186

2186번: 문자판

 

F(x, y, index): 점 (x, y)에서  index이후의 부분 문자열을 만들 수 있는 경로의 개수

점화식을 다음과 같이 설정 후, 모든 문자판을 순회하면서 F(x, y, index)의 값을 더한다.

 

 

C++ 소스코드)

 

	#include<bits/stdc++.h>
	#define endl "\n"
	#define ll long long
	#define INF 987654321
	#define MAX 17
	#define MOD 1000000000
	#define int ll
	using namespace std;
	typedef pair<int, int> p;
	p Dir[4] = { {1, 0}, {-1, 0}, {0, 1} , {0, -1} };
	int n, m, k;
	char board[101][101];
	int cache[101][101][81];
	string s;
	int solve(int x, int y, int idx) {
	int& ret = cache[x][y][idx];
	if (ret != -1)return ret;
	if (idx >= s.size()) return 1;
	ret = 0;
	for (int d = 0; d < 4; ++d) {
	for (int step = 1; step <= k; ++step) {
	int nx = x + step * Dir[d].first;
	int ny = y + step * Dir[d].second;
	if (0 <= nx && nx < n && 0 <= ny && ny < m && board[nx][ny] == s[idx])
	ret += solve(nx, ny, idx + 1);
	}
	}
	return ret;
	}
	signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	memset(cache, -1, sizeof(cache));
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < m; ++j)
	cin >> board[i][j];
	cin >> s;
	int ans = 0;
	for(int i = 0; i <n; ++i)
	for (int j = 0; j < m; ++j) {
	if (s[0] == board[i][j])
	ans += solve(i, j, 1);
	}
	cout << ans << endl;
	return 0;
	}

view raw 2186.cpp hosted with ❤ by GitHub