[백준 2186] 문자판 (DFS, DP) (C/C++) (★★★)

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <string>
#include <string.h>
using namespace std;
 
int row, col, K;
char Map[110][110];
int dp[110][110][90];
string word;
int ans;
 
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
int DFS(int x, int y, int idx)
{
    if(Map[x][y] == word[idx] && idx == word.size()-1)
    {
        return 1;
    }
    
    // dp[x][y][idx] != 0 이면 시간초과 -> dp[x][y][idx] = 0 인 경우에는 어차피 더 찾아도 없음을 뜻함 중요.. 
    if(dp[x][y][idx] != -1)
    {
        return dp[x][y][idx];
    }
    
    dp[x][y][idx] = 0; 
    
    for(int i = 0; i < 4; i++)
    {
        for(int j = 1; j <= K; j++)
        {
            int xpos = x + (dx[i] * j);
            int ypos = y + (dy[i] * j);    
            int nIdx = idx + 1;    
            
            if(safe(xpos, ypos) == 1 && Map[xpos][ypos] == word[nIdx])
            {
                dp[x][y][idx] += DFS(xpos, ypos, nIdx);
            }
        }
    }
    
    return dp[x][y][idx];
}
 
int main(void)
{
//    freopen("B2186_input.txt", "r", stdin);
    
    cin >> row >> col >> K;
    
    for(int i = 0; i < row; i++)
    {
        string temp;
        cin >> temp;
        
        for(int j = 0; j < temp.size(); j++)
        {
            Map[i][j] = temp[j];
        }
    }
    
    cin >> word;
    
    memset(dp, -1, sizeof(dp));
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(Map[i][j] == word[0])
            {
                ans += DFS(i, j, 0);
            }
        }
    }
    
    cout << ans;
    
    return 0;
}