第十四届蓝桥杯国赛 C++ B 组 G 题——AB路线（AC）

桃扇骨 2024-04-20 11:42 83阅读 0赞

#### 目录 ####

*  1. AB路线
 *   *  1. 问题描述
     *  2. 输入格式
     *  3. 输出格式
     *  4. 样例输入
     *  5. 样例输出
     *  6. 样例说明
     *  7. 评测用例规模与约定
     *  8. 原题链接
 *  2. 解题思路
 *  3. AC\_Code

## 1. AB路线 ##

前置知识点：BFS (广度优先搜索)

### 1. 问题描述 ###

有一个由  N × M N \\times M N×M 个方格组成的迷宫，每个方格写有一个字母 A 或者 B。小蓝站在迷宫左上角的方格，目标是走到右下角的方格。他每一步可以移动到上下左右相邻的方格去。

由于特殊的原因，小蓝的路线必须先走  K K K 个 A 格子、再走  K K K 个 B 格子、再走  K K K 个 A 格子、再走  K K K 个 B 格子…如此反复交替。

请你计算小蓝最少需要走多少步，才能到达右下角方格? 注意路线经过的格子数不必一定是  K K K 的倍数，即最后一段 A 或 B 的格子可以不满  K K K 个。起点保证是 A 格子。

例如  K = 3 K = 3 K=3 时，以下  3 3 3 种路线是合法的:

AAA
    AAAB
    AAABBBAAABBB

以下  3 3 3 种路线不合法:

ABABAB
    ABBBAAABBB
    AAABBBBBBBAAA

### 2. 输入格式 ###

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

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

### 3. 输出格式 ###

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

### 4. 样例输入 ###

4 4 2 
    AAAB 
    ABAB 
    BBAB 
    BAAA

### 5. 样例输出 ###

### 6. 样例说明 ###

每一步方向如下：下右下右上右下下；路线序列：AABBAABBA。

### 7. 评测用例规模与约定 ###

对于  20 % 20\\% 20% 的数据， 1 ≤ N , M ≤ 4 1 \\leq N,M \\leq 4 1≤N,M≤4。

对于另  20 % 20\\% 20% 的数据， K = 1 K = 1 K=1。

对于  100 % 100\\% 100% 的数据， 1 ≤ N , M ≤ 1000 1 \\leq N,M \\leq 1000 1≤N,M≤1000， 1 ≤ K ≤ 10 1 \\leq K \\leq 10 1≤K≤10。

### 8. 原题链接 ###

[AB路线][AB]

## 2. 解题思路 ##

在着手解决本问题之前，你需要熟悉基础的 BFS 搜索算法，具体内容可以参考这个链接：https://oi-wiki.org/graph/bfs/。

我们所熟知的 BFS 搜索模型常常是在一个迷宫中从左上角出发，目标是到达右下角，可以上下左右移动，但某些位置有陷阱无法通过，我们需要求的是最短到达时间。

这道题目的基本模型与我们熟悉的搜索模型大致相同，它们的共性包括：

*  都是从左上角出发，目标是到达右下角。
 *  都可以在四个方向进行移动。
 *  每次移动的权值都为  1 1 1。

因此，这道题很有可能可以使用 BFS 来解答。然而，我们还需要注意到它们的差异性：

*  在常见的模型中，存在无法通过的陷阱，而在这道题目中，没有陷阱，这使得题目在这一点上甚至比常见的模型更简单。
 *  在常见的模型中，除了陷阱，可以随意移动，而在这道题目中，移动受到  A,B \\text\{A,B\} A,B 格之间不能随意通行的限制。
 *  在常见的模型中，每个格子只能被访问一次，而在这道题目中，每个格子最多可以被访问  k k k 次。这一点非常重要。

接下来，我们将重点讨论最后这一点：

在常规的 BFS 算法中，我们会使用一个数组  s t i j st\_\{ij\} stij 来标识某个位置是否已经被访问过。如果该值为 `true`，则表示该位置已经被访问过，不能再次访问；如果该值为 `false`，则表示该位置尚未被访问。这种做法是保证 BFS 算法复杂度的关键，因为每个位置最多只会被访问一次。

但在这道题目中，每个位置可能会被访问多次。因为题目规定  A A A 格只能到达  A A A 格，如果想从  A A A 格到达  B B B 格，必须在第  K K K 次访问  A A A 格时才能达到， B B B 格同理。

这就意味着，每个格子最多可能会被访问  K K K 次。假设某个格子  ( i , j ) (i,j) (i,j) 的字符为  A / B A/B A/B，到达它可能是连续走了  1 , 2 , ⋯   , K 1, 2, \\cdots, K 1,2,⋯,K 个  A / B A/B A/B 格。

由于  K K K 的取值范围不大，我们可以考虑对  s t st st 数组进行扩展，定义  s t i , j , k st\_\{i,j,k\} sti,j,k 表示连续走过  k k k 个  A / B A/B A/B 格后是否能到达格子  ( i , j ) (i,j) (i,j)，如果能，标记为 `true`，否则标记为 `false`。因此，对于同一个  k k k，我们最多只会访问一个格子一次。

在进行 BFS 转移过程中，我们需要根据当前连续步数  k k k 进行分类讨论：

*  如果  k < K k<K k<K，我们只能从当前格子移动到相同字符的格子，然后  k k k 增加  1 1 1。
 *  如果  k = = K k==K k==K，我们只能从当前格子移动到不同字符的格子，然后将  k k k 重置为  1 1 1。

除此之外，所有步骤与普通的 BFS 算法相同，时间复杂度为  O ( n m k ) O(nmk) O(nmk)。

## 3. AC\_Code ##

*  C++

#include <bits/stdc++.h>
    using namespace std;
    typedef long long LL;
    const int mod = 1000000007;
    const int N = 1010;
    
    int n, m, k;
    bool st[N][N][11];
    int dx[] = {
        0, 1, 0, -1};
    int dy[] = {
        -1, 0, 1, 0};
    
    int main()
    {
        
        ios_base ::sync_with_stdio(false);
        cin.tie(0);
        cout.tie(0);
    
        cin >> n >> m >> k;
        vector<string> s(n);
    
        for (int i = 0; i < n; ++i)
        {
        
            cin >> s[i];
        }
    
        queue<array<int, 3>> q;
        q.push({
        0, 0, 1});
        st[0][0][1] = true;
    
        int ans = 0;
        while (q.size())
        {
        
            int size = q.size();
            while (size--)
            {
        
                auto p = q.front();
                q.pop();
                int x = p[0], y = p[1];
                if (x == n - 1 && y == m - 1)
                {
        
                    cout << ans << '\n';
                    return 0;
                }
                if (p[2] == k)
                {
        
                    for (int i = 0; i < 4; ++i)
                    {
        
                        int a = x + dx[i], b = y + dy[i];
                        if (a >= 0 && a < n && b >= 0 && b < m && s[a][b] != s[x][y] && !st[a][b][1])
                        {
        
                            st[a][b][1] = true;
                            q.push({
        a, b, 1});
                        }
                    }
                }
                else
                {
        
                    for (int i = 0; i < 4; ++i)
                    {
        
                        int a = x + dx[i], b = y + dy[i];
                        if (a >= 0 && a < n && b >= 0 && b < m && s[a][b] == s[x][y] && !st[a][b][p[2] + 1])
                        {
        
                            st[a][b][p[2] + 1] = true;
                            q.push({
        a, b, p[2] + 1});
                        }
                    }
                }
            }
            ans++;
        }
    
        cout << -1 << '\n';
        return 0;
    }

*  Java

import java.util.*;
    
    public class Main {
        
        public static void main(String[] args) {
        
            Scanner input = new Scanner(System.in);
            int N = 1010;
            int n = input.nextInt();
            int m = input.nextInt();
            int k = input.nextInt();
            boolean[][][] st = new boolean[N][N][11];
            int[] dx = {
        0, 1, 0, -1};
            int[] dy = {
        -1, 0, 1, 0};
            String[] s = new String[n];
            for (int i = 0; i < n; ++i) {
        
                s[i] = input.next();
            }
            Queue<int[]> q = new LinkedList<>();
            q.add(new int[]{
        0, 0, 1});
            st[0][0][1] = true;
            int ans = 0;
            while (!q.isEmpty()) {
        
                int size = q.size();
                while (size-- > 0) {
        
                    int[] p = q.poll();
                    int x = p[0], y = p[1];
                    if (x == n - 1 && y == m - 1) {
        
                        System.out.println(ans);
                        return;
                    }
                    if (p[2] == k) {
        
                        for (int i = 0; i < 4; ++i) {
        
                            int a = x + dx[i], b = y + dy[i];
                            if (a >= 0 && a < n && b >= 0 && b < m && s[a].charAt(b) != s[x].charAt(y) && !st[a][b][1]) {
        
                                st[a][b][1] = true;
                                q.add(new int[]{
        a, b, 1});
                            }
                        }
                    } else {
        
                        for (int i = 0; i < 4; ++i) {
        
                            int a = x + dx[i], b = y + dy[i];
                            if (a >= 0 && a < n && b >= 0 && b < m && s[a].charAt(b) == s[x].charAt(y) && !st[a][b][p[2] + 1]) {
        
                                st[a][b][p[2] + 1] = true;
                                q.add(new int[]{
        a, b, p[2] + 1});
                            }
                        }
                    }
                }
                ans++;
            }
            System.out.println(-1);
        }
    }

*  Python

def slove():
        n, m, k = map(int, input().split())
        s = []
        for _ in range(n):
            s.append(input())
        q = []
        q.append([0, 0, 1])
        st = [[[False] * 11 for _ in range(m)] for _ in range(n)]
        st[0][0][1] = True
        ans = 0
    
        dx = [0, 1, 0, -1]
        dy = [-1, 0, 1, 0]
        while q:
            size = len(q)
            while size > 0:
                p = q.pop(0)
                size -= 1
                x, y = p[0], p[1]
                if x == n - 1 and y == m - 1:
                    print(ans)
                    return
                if p[2] == k:
                    for i in range(4):
                        a, b = x + dx[i], y + dy[i]
                        if 0 <= a < n and 0 <= b < m and s[a][b] != s[x][y] and not st[a][b][1]:
                            st[a][b][1] = True
                            q.append([a, b, 1])
                else:
                    for i in range(4):
                        a, b = x + dx[i], y + dy[i]
                        if 0 <= a < n and 0 <= b < m and s[a][b] == s[x][y] and not st[a][b][p[2] + 1]:
                            st[a][b][p[2] + 1] = True
                            q.append([a, b, p[2] + 1])
            ans += 1
        print(-1)
    
    
    slove()

[AB]: https://www.lanqiao.cn/problems/6265/learning/