P9425 [蓝桥杯 2023 国 B] AB 路线

有一个由 $N \times M$ 个方格组成的迷宫，每个方格写有一个字母 `A` 或者 `B`。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。 由于特殊的原因，小蓝的路线必须先走 $K$ 个 `A` 格子、再走 $K$ 个 `B` 格子、再走 $K$ 个 `A` 格子、再走 $K$ 个 `B` 格子……如此反复交替。 请你计算小蓝最少需要走多少步，才能到达右下角方格？ 注意路线经过的格子数不必一定是 $K$ 的倍数，即最后一段 `A` 或 `B` 的格子可以不满 $K$ 个。起点保证是 `A` 格子。 例如 $K = 3$ 时，以下 $3$ 种路线是合法的： ```plain AA AAAB AAABBBAAABBB ``` 以下 $3$ 种路线不合法： ```plain ABABAB ABBBAAABBB AAABBBBBBAAA ```

第一行包含三个整数 $N$、$M$ 和 $K$。 以下 $N$ 行，每行包含 $M$ 个字符（`A` 或 `B`），代表格子类型。

一个整数，代表最少步数。如果无法到达右下角，输出 $-1$。

### 样例说明 每一步方向如下：下右下右上右下下；路线序列： `AABBAABBA`。 ### 评测用例规模与约定 - 对于 $20\%$ 的数据，$1 \le N, M \le 4$。 - 对于另 $20\%$ 的数据，$K = 1$。 - 对于 $100\%$ 的数据，$1 \le N, M \le 1000$，$1 \le K \le 10$。 第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 G 题