[蓝桥杯 2023 国 B] AB 路线 （BFS)

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

AA
AAAB
AAABBBAAABBB

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

ABABAB
ABBBAAABBB
AAABBBBBBAAA

输入格式

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

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

输出格式

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

输入输出样例 #1

输入 #1

4 4 2
AAAB
ABAB
BBAB
BAAA

输出 #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 题

关键解题思路

1. 状态定义：

   • 使用广度优先搜索(BFS)来寻找最短路径
   • 状态需要记录当前位置(x,y)、已走步数s、当前应该走的格子类型(flag)
   • flag为false表示当前应该走A格子，true表示当前应该走B格子

2. 状态转移规则：

   • 每走一步，步数s加1
   • 当步数s是K的倍数时，需要切换格子类型(flag取反)
   • 下一步只能走到相邻的、与当前要求格子类型相同的格子

3. 访问标记优化：

   • 使用四维数组vis[x][y][s%k][flag]来标记已访问状态
   • 只需要记录s对K取模的结果，因为我们只关心当前是否需要切换格子类型

4. 终止条件：

   • 当到达右下角(n,m)时，返回已走步数s
   • 如果队列为空仍未到达终点，则返回-1

5. 特殊处理：

   • 起点保证是A格子，所以初始flag为false
   • 最后一段A或B的格子可以不满K个，这通过状态转移时检查当前格子类型实现

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n, m, k, ans = 1000000, mv[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
bool vis[1002][1002][12][2];
char a[1002][1002],c[2] = {'A', 'B'};struct node {int x, y, s;bool flag; 
};bool check(int x, int y, int s, bool flag) {return x < 1 || y < 1 || x > n || y > m ||  vis[x][y][s%k][flag] || c[flag] != a[x][y];
}void bfs() {vis[1][1][0][false] = true;queue<node> q;q.push({1, 1, 0, false});while (!q.empty()) {node cur = q.front();q.pop();int x = cur.x, y = cur.y, s = cur.s;bool flag = cur.flag;if (x == n && y == m) {ans = min(ans, s);return;}int next_s = s + 1;bool next_flag = flag;if (next_s % k == 0) {next_flag = !flag;}for (int i = 0; i < 4; ++i) {int xi = x + mv[i][0], yi = y + mv[i][1];if (check(xi, yi, next_s, next_flag)) continue;vis[xi][yi][next_s%k][next_flag] = true;q.push({xi, yi, next_s, next_flag});}}
}int main() {cin >> n >> m >> k;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {cin >> a[i][j];}}bfs();if (ans == 1000000) cout << -1;else cout << ans;return 0;
}

其实dfs也能做，但是会超时

#include<bits/stdc++.h>
using namespace std;
int n, m, k, ans = 1e9, mv[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
string s[1010];
bool vis[1010][1010][12][2]; 
char c[2] = {'A', 'B'};bool check(int x, int y, int cnt, bool flag) {return x < 0 || y < 0 || x >= n || y >= m || vis[x][y][cnt%k][flag] || c[flag] != s[x][y];
}void dfs(int x, int y, int cnt, bool flag) {if (x == n-1 && y == m-1) {ans = min(ans, cnt);return;}int next_cnt = cnt + 1;bool next_flag = flag;if (next_cnt % k == 0) {next_flag = !flag;}for (int i = 0; i < 4; ++i) {int dx = mv[i][0] + x, dy = mv[i][1] + y;if (check(dx, dy, next_cnt, next_flag)) continue;vis[dx][dy][next_cnt%k][next_flag] = true;dfs(dx, dy, next_cnt, next_flag);vis[dx][dy][next_cnt%k][next_flag] = false;}
}int main() {cin >> n >> m >> k;for (int i = 0; i < n; ++i) {cin >> s[i];}vis[0][0][0][false] = true;dfs(0, 0, 0, false);if (ans == 1e9) cout << -1;else cout << ans;return 0;
}