Birthday Present?!

We can use Dynamic Programming to solve this problem. Here $dp_{ij}$ denotes the minimum possible cost needed to move the token to the cell $(i,j)$.

To calculate $dp_{ij}$ Let,
$P$ = min of $dp_{iy}+T+(j-y)$ for $y$ in range $[j-L,j-1]$
$Q$ = min of $dp_{xj}+T+(i-x)$ for $x$ in range $[i-L,i-1]$

(Considering the valid cells inside the grid and those which don’t require building a bridge over a blocked cell).

Now, $dp_{ij}$ = $min(P,Q)$

$dp_{iy}+T+(j-y)$ can be written as $(dp_{iy}-y)+(T+j)$ for $y$ in range $[j-L,j-1]$. As $(T+j)$ is not dependent on the previous cells, we are interested in the minimum value of $(dp_{iy}-y)$ for $y$ in the range $[j-L,j-1]$.

Now to get the minimum value, we can maintain a monotonic deque(similar to monotonic queues, but allows us to pop elements from both ends) and store $(dp_{ij}-j)$ for the relevant cells among all the cells we visit.

$Q$ can be retrieved in the same manner but we need $M$ deques for $M$ columns.

Using monotonic deques we can get an $O(NM)$ solution.

Author’s solution: https://ideone.com/wO7IUJ

Here is a blog on monotonic queue if you are not familiar with it: https://jojozhuang.github.io/algorithm/data-structure-monotonic-queue/