{"raw_statement":[{"iden":"statement","content":"有一个由 $N \\times M$ 个方格组成的迷宫，每个方格写有一个字母 `A` 或者 `B`。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。\n\n由于特殊的原因，小蓝的路线必须先走 $K$ 个 `A` 格子、再走 $K$ 个 `B` 格子、再走 $K$ 个 `A` 格子、再走 $K$ 个 `B` 格子……如此反复交替。\n\n请你计算小蓝最少需要走多少步，才能到达右下角方格？\n\n注意路线经过的格子数不必一定是 $K$ 的倍数，即最后一段 `A` 或 `B` 的格子可以不满 $K$ 个。起点保证是 `A` 格子。\n\n例如 $K = 3$ 时，以下 $3$ 种路线是合法的：\n\n```plain\nAA\nAAAB\nAAABBBAAABBB\n```\n\n以下 $3$ 种路线不合法：\n\n```plain\nABABAB\nABBBAAABBB\nAAABBBBBBAAA\n```"},{"iden":"input","content":"第一行包含三个整数 $N$、$M$ 和 $K$。\n\n以下 $N$ 行，每行包含 $M$ 个字符（`A` 或 `B`），代表格子类型。\n\n"},{"iden":"output","content":"一个整数，代表最少步数。如果无法到达右下角，输出 $-1$。"},{"iden":"note","content":"### 样例说明\n\n每一步方向如下：下右下右上右下下；路线序列： `AABBAABBA`。\n\n### 评测用例规模与约定\n\n - 对于 $20\\%$ 的数据，$1 \\le N, M \\le 4$。\n - 对于另 $20\\%$ 的数据，$K = 1$。\n - 对于 $100\\%$ 的数据，$1 \\le N, M \\le 1000$，$1 \\le K \\le 10$。\n \n第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 G 题"}],"translated_statement":null,"sample_group":[["4 4 2\nAAAB\nABAB\nBBAB\nBAAA","8"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}