You are given three integers m, n, and k.

Construct an m $\times$ n grid of characters representing a matrix where:

• '.' represents an empty cell.

• '#' represents an obstacle.

A valid path starts at the top-left cell (0, 0) and ends at the bottom-right cell (m - 1, n - 1), moving only one cell right or one cell down at each step, without visiting any obstacle cell.

Return a list of strings representing any valid m $\times$ n grid that has exactly k distinct valid paths from (0, 0) to (m - 1, n - 1). If no such grid can be formed, return an empty list.

Note: If there are multiple valid answers, you may return any of them.

Constraints:

• $1 \leq$ m, n $\leq 10$

• $1 \leq$ k $\leq 4$

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.