打卡信奥刷题（1852）用C++实现信奥 P9425 [蓝桥杯 2023 国 B] AB 路线

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$ 种路线是合法的：

AAAAABAAABBBAAABBB

以下 $3$ 种路线不合法：

ABABABABBBAAABBBAAABBBBBBAAA

输入格式

第一行包含三个整数 $N$、$M$ 和 $K$。

以下 $N$ 行，每行包含 $M$ 个字符（A 或 B），代表格子类型。

输出格式

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

输入输出样例 #1

输入 #1

4 4 2AAABABABBBABBAAA

输出 #1

8

说明/提示

样例说明

每一步方向如下：下右下右上右下下；路线序列： 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 题

C++实现

#include using namespace std;#define in cin#define out cout#define int long long //防止溢出//基础定义struct node {int x, y, cnt, r;char ch;};queue<node> q;int n, m, dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, 1, -1}, k, minx = -1;char maps[1005][1005];bool vis[1005][1005][15];signed main() {in >> n >> m >> k;for (int i = 0; i < n; i++) //输入地图for(int j = 0; j < m; j++)in >> maps[i][j];vis[0][0][0] = true, q.push({0, 0, 1, 0, \'A\'});while (!q.empty()) { //广搜int ux = q.front().x, uy = q.front().y, ucnt = q.front().cnt, ur = q.front().r;char uch = q.front().ch;q.pop();if (ux == n - 1 && uy == m - 1) {out << ur; //可以到达return 0;}if (ucnt == k) if (uch == \'A\')uch = \'B\', ucnt = 0;elseuch = \'A\', ucnt = 0;for (int i = 0; i < 4; i++) {int tx = dx[i] + ux, ty = uy + dy[i];if (tx >= 0 && ty >= 0 && tx < n && ty < m && maps[tx][ty] == uch && !vis[tx][ty][ucnt + 1])q.push({tx, ty, ucnt + 1, ur + 1, uch}), vis[tx][ty][ucnt + 1] = true; //入队并直接标记}}out << -1; //不可以到达，输出-1return 0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容