백준 2418번 단어 격자 C++

출처 : https://www.acmicpc.net/problem/2418

 

1. 3차원 dp 배열을 만든다. dp[ 행 ] [ 열 ] [ 문자열 크기 ]

2. 문자열의 0번 원소와 같은 행과 열의 dp [ 행 ][ 열 ][0] 을 1로 설정한다.

3. k를 1부터 문자열 크기 - 1 까지순회하면서 k번째 원소와 같고 주변에 k-1번째 원소가 있다면 dp[i][j][k]에

dp[주변 행][주변 열][k - 1]을 더해준다.

4. 모든 dp[행][열][문자열 크기 - 1]을 더한다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>

using namespace std;
using ll = long long;

int dRow[8] = { -1,-1,0,1,1,1,0,-1 };
int dCol[8] = { 0,1,1,1,0,-1,-1,-1 };

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

	int h, w, l;
	cin >> h >> w >> l;
	vector<vector<char>> board(h, vector<char>(w));
	vector<vector<vector<ll>>> dp(h, vector<vector<ll>>(w, vector<ll>(l, 0)));
	string str, target;
	for (int i = 0; i < h; i++) {
		cin >> str;
		for (int j = 0; j < w; j++) {
			board[i][j] = str[j];
		}
	}
	cin >> target;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			if (board[i][j] == target[0]) dp[i][j][0] = 1;
		}
	}

	for (int k = 1; k < l; k++) {
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				if (board[i][j] != target[k]) continue;
				for (int y = 0; y < 8; y++) {
					int nextRow = i + dRow[y];
					int nextCol = j + dCol[y];
					if (nextRow < 0 || nextRow >= h) continue;
					if (nextCol < 0 || nextCol >= w) continue;
					if (board[nextRow][nextCol] != target[k - 1]) continue;
					dp[i][j][k] += dp[nextRow][nextCol][k - 1];
				}
			}
		}
	}
	ll sum = 0;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			sum += dp[i][j][l - 1];
		}
	}
	cout << sum;
};