First, let us estimate the number of conforming paths.

• Choice of \((x_0,y_0)\): at most \(HW\) cases.
• Choice of \((x_1,y_1)\): at most \(4\) cases, as it is chosen from one of the four squares adjacent to \((x_0,y_0)\).
• Choice of \((x_k,y_k)\;(2 \leq k \leq K)\): at most \(3\) cases, as it is chosen from one of the four squares adjacent to \((x_{k-1},y_{k-1})\) except for \((x_{k-2},y_{k-2})\).

Overall, the number of conforming paths is at most \(HW \times 4 \times 3^{K-1} \leq 2.3 \times 10^7\). This count is small enough to enumerate exhaustively within the execution time limit.

To enumerate the possible paths, it is convenient to use Depth-First Search (DFS). Maintain (the current position, the number of operations, already-visited squares), and recursively try all possible next moves, to iterate through the paths.

Sample code (Python)

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

ans = 0
# The array to record the already visited squares
visited = [[False] * W for _ in range(H)]


# Start from the state where k moves have been made and being at square (i, j)
def rec(i, j, k):
    global ans
    if k == K:
        # If K moves have been made, add 1 to the answer and terminate
        ans += 1
        return
    # Mark (i, j) as visited
    visited[i][j] = True
    # Try moves to adjacent four squares
    for di, dj in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        ni, nj = i + di, j + dj
        # If the square you are moving into is within the grid, empty, and unvisited, move there and go on recursively
        if 0 <= ni < H and 0 <= nj < W and S[ni][nj] == "." and not visited[ni][nj]:
            rec(ni, nj, k + 1)
    # Mark (i, j) as unvisited
    visited[i][j] = False


# Try all (i0, j0)
for i in range(H):
    for j in range(W):
        if S[i][j] == ".":
            rec(i, j, 0)
print(ans)