Problem Description

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:

AA
AAAB
AAABBBAAABBB

The following $3$ routes are invalid:

ABABAB
ABBBAAABBB
AAABBBBBBAAA

Input Format

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 Format

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

4 4 2
AAAB
ABAB
BBAB
BAAA

8

Hint

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