P9425 [Lanqiao Cup 2023 National B] AB Route

There is a maze consisting of $N \times M$ cells. Each cell contains the letter `A` or `B`. Xiao Lan starts at the top-left cell of the maze, and his goal is to reach the bottom-right cell. In each step, he may move to an adjacent cell in one of the four directions: up, down, left, or right. For special reasons, Xiao Lan's route must first go through $K$ `A` cells, then $K$ `B` cells, then $K$ `A` cells, then $K$ `B` cells, and so on, alternating repeatedly. Please compute the minimum number of steps Xiao Lan needs to take to reach the bottom-right cell. Note that the number of cells visited along the route does not have to be a multiple of $K$. That is, the last segment of `A` or `B` cells may contain fewer than $K$ cells. The starting cell is guaranteed to be an `A` cell. For example, when $K = 3$, the following $3$ routes are valid: ```plain AA AAAB AAABBBAAABBB ``` The following $3$ routes are invalid: ```plain ABABAB ABBBAAABBB AAABBBBBBAAA ```

The first line contains three integers $N$, $M$, and $K$. The next $N$ lines each contain $M$ characters (`A` or `B`), representing the type of each cell.

Output one integer, the minimum number of steps. If it is impossible to reach the bottom-right cell, output $-1$.

### Sample Explanation The directions for each step are: down, right, down, right, up, right, down, down. The route sequence is: `AABBAABBA`. ### Constraints - For $20\%$ of the testdata, $1 \le N, M \le 4$. - For another $20\%$ of the testdata, $K = 1$. - For $100\%$ of the testdata, $1 \le N, M \le 1000$, $1 \le K \le 10$. 14th Lanqiao Cup Software Competition Finals, C/C++ University Group B, Problem G. Translated by ChatGPT 5