一、视频讲解

[蓝桥杯]真题讲解：AB路线（BFS+分层图）

二、正解代码

1、C++

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
const int N = 1e3 + 10;
int g[N][N];
bool st[N][N][20];
int dis[N][N][20];int n, m, k;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};bool check(int x, int y) {return x >= 0 && x < n && y >= 0 && y < m;
}int bfs() {for(int i = 0; i < n; i ++) {for(int j = 0; j < m; j ++) {for(int p = 0; p < k; p ++) {dis[i][j][p] = INF;}}}queue<array<int,3>>q;q.push({0, 0, 1});dis[0][0][1] = 1;st[0][0][1] = true;while(q.size()){auto t = q.front();q.pop();int x = t[0], y = t[1], cnt = t[2];int d = dis[x][y][cnt];for(int i = 0; i < 4; i ++) {int nx = x + dx[i];int ny = y + dy[i];int nc = (d / k) % 2;if(check(nx, ny) && g[nx][ny] == nc && !st[nx][ny][(d + 1) % k]) {st[nx][ny][(d + 1) % k] = true;q.push({nx, ny, (d + 1) % k});dis[nx][ny][(d + 1) % k] = d + 1;}}}int minv = INF;for(int i = 0; i < k; i ++) {minv = min(minv, dis[n - 1][m - 1][i]);}return minv;
}void solve(){cin >> n >> m >> k;for(int i = 0; i < n; i ++) {string s; cin >> s;for(int j = 0; j < m; j ++) {g[i][j] = (s[j] != 'A');}}int res = bfs();if(res == INF){cout << -1 << endl;}else{cout << res - 1 << endl;}}int main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t = 1;while(t--){solve();}return 0;
}

2、python3

from collections import deque
INF = 0x3f3f3f3f
N = 1010
n, m, k = map(int, input().split())
st = [[[False] * 20 for _ in range(N)] for _ in range(N)]
dis = [[[INF] * 20 for _ in range(N)] for _ in range(N)]
g = [[0] * N for _ in range(N)]
dx = [-1, 0, 1, 0]
dy = [0, 1, 0, -1]def check(x, y):return x >= 0 and x < n and y >= 0 and y < mdef bfs():q = deque([(0, 0, 1)])dis[0][0][1] = 1st[0][0][1] = Truewhile q:x, y, cnt = q[0]q.popleft()d = dis[x][y][cnt]for i in range(4):nx = x + dx[i]ny = y + dy[i]nc = (d // k) % 2if check(nx, ny) and g[nx][ny] == nc and st[nx][ny][(d + 1) % k] == False:st[nx][ny][(d + 1) % k] = Trueq.append((nx, ny, (d + 1) % k))dis[nx][ny][(d + 1) % k] = d + 1minv = INFfor i in range(k):minv = min(minv, dis[n - 1][m - 1][i])return minvfor i in range(n):s = input()for j in range(m):if s[j] != 'A':g[i][j] = 1else:g[i][j] = 0
res = bfs()
if res == INF:print(-1)
else:print(res - 1)

3、Java

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;public class ABRoad {public static final int INF = 0x3f3f3f3f;public static int[] dx = new int[]{-1, 0, 1, 0};public static int[] dy = new int[]{0, 1, 0, -1};public static int n, m, k;public static int[][] g;public static boolean[][][] st;public static int[][][] dis;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();m = sc.nextInt();k = sc.nextInt();g = new int[n + 10][m + 10];st = new boolean[n + 10][m + 10][k + 10];dis = new int[n + 10][m + 10][k + 10];for(int i = 0; i < n; i ++ ) {String s;s = sc.next();for(int j = 0; j < m; j ++) {if(s.charAt(j) != 'A')g[i][j] = 1;elseg[i][j] = 0;}}int res = bfs();if(res == INF)System.out.println(-1);elseSystem.out.println(res - 1);}private static int bfs() {for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {for (int p = 0; p < k; p++) {dis[i][j][p] = INF;}}}Queue<int[]> q = new LinkedList<>();q.add(new int[]{0, 0, 1});dis[0][0][1] = 1;st[0][0][1] = true;while (!q.isEmpty()) {int[] t = q.poll();int x = t[0], y = t[1], cnt = t[2];int d = dis[x][y][cnt];for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];int nc = (d / k) % 2;if (check(nx, ny) && g[nx][ny] == nc && !st[nx][ny][(d + 1) % k]) {st[nx][ny][(d + 1) % k] = true;q.add(new int[]{nx, ny, (d + 1) % k});dis[nx][ny][(d + 1) % k] = d + 1;}}}int minv = INF;for(int i = 0; i < k; i ++) {minv = Math.min(minv, dis[n - 1][m - 1][i]);}return  minv;}private static boolean check(int x, int y) {return x >= 0 && x < n && y >= 0 && y < m;}
}