{"problem":{"name":"[蓝桥杯 2023 国 B] AB 路线","description":{"content":"有一个由 $N \\times M$ 个方格组成的迷宫，每个方格写有一个字母 `A` 或者 `B`。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。 由于特殊的原因，小蓝的路线必须先走 $K$ 个 `A` 格子、再走 $K$ 个 `B` 格子、再走 $K$ 个 `A` 格子、再走 $K$ 个 `B` 格子……如此反复交替。 请你计算小蓝最少需要走多少步，","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P3"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9425"},"statements":[{"statement_type":"Markdown","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```\n\n## Input\n\n第一行包含三个整数 $N$、$M$ 和 $K$。\n\n以下 $N$ 行，每行包含 $M$ 个字符（`A` 或 `B`），代表格子类型。\n\n## Output\n\n一个整数，代表最少步数。如果无法到达右下角，输出 $-1$。\n\n[samples]\n\n## Note\n\n### 样例说明\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 题","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9425","tags":["2023","广度优先搜索 BFS","蓝桥杯国赛"],"sample_group":[["4 4 2\nAAAB\nABAB\nBBAB\nBAAA","8"]],"created_at":"2026-03-03 11:09:25"}}