Unique Paths with K Steps

Problem Statement:

You are given an \(n \times m\) grid consisting of cells that are either open (denoted by '.') or blocked (denoted by '#'). Starting from the top-left cell, your goal is to reach the bottom-right cell by moving only to the right or down.

You are also given an integer \(k\) which represents the maximum number of steps allowed. A step is defined as a move from a cell to an adjacent cell in the allowed directions (right or down). Note that a valid path may use fewer than or equal to \(k\) steps.

Formally, if \(dp[i][j][s]\) represents the number of ways to reach cell \((i, j)\) in exactly \(s\) steps, then your task is to compute the sum: \[ \sum_{s=0}^{k} dp[n-1][m-1][s] \] where movements from cell \((i, j)\) can only come from the cell above \((i-1, j)\) or the cell to the left \((i, j-1)\), provided there is no obstacle.

If the starting cell or the destination cell is blocked, the answer is \(0\).

inputFormat

The first line contains three space-separated integers \(n\), \(m\), and \(k\), where \(n\) and \(m\) represent the dimensions of the grid and \(k\) is the maximum number of steps allowed.

The following \(n\) lines each contain a string of length \(m\) consisting of the characters '.' and '#' representing the grid.

outputFormat

Output a single integer representing the number of unique valid paths from the top-left cell to the bottom-right cell with at most \(k\) steps.

3 3 4
...
.#.
...

2