まず，条件を満たす経路の個数を見積もってみましょう．

• \((x_0,y_0)\) の選び方：たかだか \(HW\) 通り
• \((x_1,y_1)\) の選び方： \((x_0,y_0)\) の上下左右に隣接しているマスから選ばれるから，たかだか \(4\) 通り
• \((x_k,y_k)\;(2 \leq k \leq K)\) の選び方： \((x_{k-1},y_{k-1})\) の上下左右に隣接しているたかだか \(4\) マスのうち， \((x_{k-2},y_{k-2})\) と異なるマスから選ばれるから，たかだか \(3\) 通り

以上を合わせて，条件を満たす経路の個数は \(HW \times 4 \times 3^{K-1} \leq 2.3 \times 10^7\) です．このくらいであれば，可能な経路をすべて列挙しても実行時間制限に間に合います．

可能な経路の列挙は， 深さ優先探索 を使うのが便利です．（現在の位置，移動回数，すでに訪れたマス）の状態を持っておいて，次に移動できる場所をすべて試して再帰的に計算することで，経路を列挙することができます．

実装例 (Python)

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]

ans = 0
# すでに訪れたマスを記録する配列
visited = [[False] * W for _ in range(H)]


# k 回移動してマス (i, j) にいる状態から探索を開始する
def rec(i, j, k):
    global ans
    if k == K:
        # K 回移動することができたら，答えに 1 を足して探索を終了
        ans += 1
        return
    # (i, j) を訪問済として記録する
    visited[i][j] = True
    # 隣接する 4 マスへの移動を試す
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        # 移動先がマス目の中にあり，空きマスであり，まだ訪れていないならば，そこへ移動し再帰的に探索する
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == "." and not visited[ni][nj]:
            rec(ni, nj, k + 1)
    # (i, j) を訪れなかったことにする
    visited[i][j] = False


# (i0, j0) をすべて試す
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            rec(i, j, 0)
print(ans)