### 问题描述 有一个由 $N \times M$ 个方格组成的迷宫，每个方格写有一个字母 A 或者 B。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。 由于特殊的原因，小蓝的路线必须先走 $K$ 个 A 格子、再走 $K$ 个 B 格子、再走 $K$ 个 A 格子、再走 $K$ 个 B 格子......如此反复交替。 请你计算小蓝最少需要走多少步，才能到达右下角方格? 注意路线经过的格子数不必一定是 $K$ 的倍数，即最后一段 A 或 B 的格子可以不满 $K$ 个。起点保证是 A 格子。 例如 $K = 3$ 时，以下 $3$ 种路线是合法的: ```text AAA AAAB AAABBBAAABBB ``` 以下 $3$ 种路线不合法: ```text ABABAB ABBBAAABBB AAABBBBBBBAAA ``` ### 输入格式 第一行包含三个整数 $N$、$M$ 和 $K$。 以下 $N$ 行，每行包含 $M$ 个字符 ( A 或 B )，代表格子类型。 ### 输出格式 一个整数，代表最少步数。如果无法到达右下角，输出 $−1$。 ### 样例输入 ```text 4 4 2 AAAB ABAB BBAB BAAA ``` ### 样例输出 ```text 8 ``` ### 样例说明 每一步方向如下：下右下右上右下下；路线序列：AABBAABBA。 ### 评测用例规模与约定 对于 $20\\%$ 的数据，$1 \leq N,M \leq 4$。 对于另 $20\\%$ 的数据，$K = 1$。 对于 $100\\%$ 的数据，$1 \leq N,M \leq 1000$，$1 \leq K \leq 10$。