P1535 [USACO08MAR] Cow Travelling S

Cows wander on a pasture divided into $N$ rows and $M$ columns ($2 \leq N, M \leq 100$), trying to find the tastiest grass. At some moment, Farmer John sees Bessie at position $(R_1, C_1)$. Exactly $T$ ($0 < T \leq 15$) seconds later, FJ runs into Bessie at position $(R_2, C_2)$. FJ does not know whether Bessie visited $(R_2, C_2)$ at any time during those $T$ seconds; he only knows that she is there now. Let $S$ be the number of paths the cow can take to go from $(R_1, C_1)$ to $(R_2, C_2)$ in $T$ seconds. FJ wants a program to compute this value. Each second, the cow moves horizontally or vertically by a distance of $1$ (the cow is always moving and will not stay at the same point in any second). Some places on the pasture have trees. Of course, the cow cannot step on a tree, and she will not leave the pasture. You are given a map of the whole pasture, where `.` means open grass and `*` means a blocking tree. Your task is to compute how many different paths a cow can take to move from $(R_1, C_1)$ to $(R_2, C_2)$ in $T$ seconds.

The first line contains $3$ space-separated integers: $N, M, T$. Then $N$ lines follow: the $i$-th line has $M$ consecutive characters describing row $i$ of the pasture. Each character is guaranteed to be either `.` or `*`. The last line contains $4$ integers $R_1, C_1, R_2, C_2$.

Output the number of ways to move from $(R_1, C_1)$ to $(R_2, C_2)$.

There is only one way for the cow to go from $(1, 3)$ to $(1, 5)$ in $6$ seconds, by going around the tree in front of her. Translated by ChatGPT 5