[2186] 문자판

오랜만에 삽질했네 ^^

let p = readLine()!.split(separator: " ").map{Int(String($0))!}
let (n,m,k) = (p[0],p[1],p[2])
var dp = Array(repeating: Array(repeating: Array(repeating: -1, count: 81), count: m), count: n)
var d = [(Int,Int)]()
var arr = [[String]]()
var target = [String]()
var cnt = 0

for i in 1...k {
d.append(contentsOf: [(0,i),(0,-i),(i,0),(-i,0)])
}
for _ in 0..<n {
    arr.append(readLine()!.map{String($0)})
}
target = readLine()!.map{String($0)}


func dfs(_ r:Int,_ c:Int,_ index:Int,_ dp:inout[[[Int]]])-> Int {
    if dp[r][c][index] != -1 {   // 재방문
       return dp[r][c][index]    // 0 or cnt
    }
    if target.count == index {  // 새롭게 단어를 만들어 냈을 때 cnt++
       return 1
    }
    dp[r][c][index] = 0 // 방문 처리
    
    for (x,y) in d {
        let (nx,ny) = (r+x, c+y)
        if 0<=nx, nx<n, 0<=ny, ny<m {
            if arr[nx][ny] == target[index] {
                dp[r][c][index] += dfs(nx, ny, index+1, &dp)
            }
        }
    }
    return dp[r][c][index]
}

for i in 0..<n {
    for j in 0..<m {
        if arr[i][j] == target[0] {   // 첫 문자에서 끝까지 갈 수 있는지.
            cnt += dfs(i, j, 1, &dp)

        }
    }
}
print(cnt)