题目描述

给定一个有N行M列的字符矩阵，每个位置上是一个字母A或B。从左上角出发，每次可以向右或向下走一步，直到到达右下角。每次经过一个位置时，如果该位置上的字母是A，则可以获得一次移动机会，最多可以累积K次；如果该位置上的字母是B，则必须消耗一次移动机会，如果没有移动机会则无法继续前进。求最少需要多少步才能到达右下角，如果无法到达则输出-1。

输入格式

第一行包含三个整数N、M和K，表示矩阵的行数、列数和最大移动机会。

接下来N行，每行包含M个字符，表示矩阵的内容。

输出格式

输出一个整数，表示最少需要多少步才能到达右下角，如果无法到达则输出-1。

样例输入

3 3 1
ABA
BAB
ABA

样例输出

4

解题思路

本题可以使用广度优先搜索（BFS）算法来求解。BFS是一种遍历或搜索图或树数据结构的算法，它从一个起始节点开始，按照层次顺序依次访问所有节点。BFS通常需要一个队列数据结构来存储待访问的节点。

对于本题，我们可以把矩阵看作一个有N*M个节点和若干条边的图，每个节点对应一个位置，每个位置可以向右或向下走一步到达相邻的位置。我们用一个结构体Cell来表示一个节点，包含四个属性：row、col、steps和remainingMoves，分别表示当前位置的行号、列号、已经走过的步数和剩余的移动机会。我们用一个队列来存储待访问的节点，并用一个二维布尔数组visited来记录每个位置是否被访问过。具体地，我们做以下操作：

• 定义一个队列q，并把起始节点（0,0,0,K）加入队列；
• 定义一个二维布尔数组visited，并把起始位置（0,0）标记为已访问；
• 定义两个整数数组dr和dc，分别表示向右或向下走一步时行号和列号的变化；
• 当队列不为空时，重复以下步骤：
• 取出队列的第一个节点curr；
• 如果curr的位置是右下角（N-1,M-1），则返回curr的步数；
• 遍历curr的位置的四个方向；
• 计算下一个位置的行号和列号nextRow和nextCol；
• 如果nextRow和nextCol在矩阵范围内且没有被访问过，则进行以下操作：
  • 计算下一个位置剩余的移动机会nextMoves；
  • 如果当前位置上的字母是A，则判断nextMoves是否为0，如果是，则将nextMoves设为K；否则判断nextMoves是否为1，如果是，则将nextMoves设为-1；否则将nextMoves减一；
  • 如果当前位置上的字母是B，则判断nextMoves是否为0，如果是，则将nextMoves设为-1；否则判断nextMoves是否大于0，如果是，则将nextMoves减一；
  • 如果nextMoves不为-1，则把下一个节点（nextRow,nextCol,curr.steps+1,nextMoves）加入队列，并把下一个位置（nextRow,nextCol）标记为已访问；
• 如果队列为空，说明无法到达右下角，返回-1。

//G.AB路径
#include <bits/stdc++.h> // 引入万能头文件

using i64 = long long; // 定义i64为long long的别名

// 定义一个结构体Cell，表示一个节点，包含四个属性：row、col、steps和remainingMoves，分别表示当前位置的行号、列号、已经走过的步数和剩余的移动机会
struct Cell {
    i64 row;
    i64 col;
    i64 steps;
    i64 remainingMoves;
};

// 定义一个函数findShortestPath，接受两个参数：一个由字符组成的二维向量maze，表示矩阵的内容；一个整数K，表示最大移动机会。返回最少需要多少步才能到达右下角，如果无法到达则返回-1
i64 findShortestPath(std::vector<std::vector<char>> &maze, i64 K) {
    i64 N = maze.size(); // 定义一个i64变量N，表示矩阵的行数
    i64 M = maze[0].size(); // 定义一个i64变量M，表示矩阵的列数
    std::vector<std::vector<bool>> visited(N, std::vector<bool>(M, false)); // 定义一个二维布尔向量visited，表示每个位置是否被访问过，大小为N*M，初始为false
    i64 dr[] = {-1, 0, 1, 0}; // 定义一个整数数组dr，表示向右或向下走一步时行号的变化
    i64 dc[] = {0, 1, 0, -1}; // 定义一个整数数组dc，表示向右或向下走一步时列号的变化
    std::queue<Cell> q; // 定义一个队列q，用来存储待访问的节点
    q.push({0, 0, 0, K}); // 把起始节点（0,0,0,K）加入队列
    visited[0][0] = true; // 把起始位置（0,0）标记为已访问
    while (!q.empty()) { // 当队列不为空时
        Cell curr = q.front(); // 取出队列的第一个节点curr
        q.pop(); // 弹出队列的第一个节点
        if (curr.row == N - 1 && curr.col == M - 1) { return curr.steps; } // 如果curr的位置是右下角（N-1,M-1），则返回curr的步数
        for (i64 i = 0; i < 4; i++) { // 遍历curr的位置的四个方向
            i64 nextRow = curr.row + dr[i]; // 计算下一个位置的行号nextRow
            i64 nextCol = curr.col + dc[i]; // 计算下一个位置的列号nextCol
            if (nextRow >= 0 && nextRow < N && nextCol >= 0 && nextCol < M && !visited[nextRow][nextCol]) { // 如果nextRow和nextCol在矩阵范围内且没有被访问过，则进行以下操作：
                i64 nextMoves = curr.remainingMoves; // 计算下一个位置剩余的移动机会nextMoves
                if (maze[curr.row][curr.col] == 'A') { // 如果当前位置上的字母是A，则判断nextMoves是否为0，如果是，则将nextMoves设为K；否则判断nextMoves是否为1，如果是，则将nextMoves设为-1；否则将nextMoves减一；
                    if (nextMoves == 0) { nextMoves = K; }
                    else if (nextMoves == 1) { nextMoves = -1; }
                    else { nextMoves--; }
                } else { // 如果当前位置上的字母是B，则判断nextMoves是否为0，如果是，则将nextMoves设为-1；否则判断nextMoves是否大于0，如果是，则将nextMoves减一；
                    if (nextMoves == 0) { nextMoves = -1; }
                    else if (nextMoves > 0) { nextMoves--; }
                }
                if (nextMoves != -1) { // 如果nextMoves不为-1，则把下一个节点（nextRow,nextCol,curr.steps+1,nextMoves）加入队列，并把下一个位置（nextRow,nextCol）标记为已访问；
                    q.push({nextRow, nextCol, curr.steps + 1, nextMoves});
                    visited[nextRow][nextCol] = true;
                }
            }
        }
    }
    return -1; // 如果队列为空，说明无法到达右下角，返回-1
}

// 主函数
int main() {
    i64 N, M, K; // 定义三个i64变量N、M和K，分别表示矩阵的行数、列数和最大移动机会
    std::cin >> N >> M >> K; // 输入N、M和K的值
    std::vector<std::vector<char>> maze(N, std::vector<char>(M)); // 定义一个由字符组成的二维向量maze，表示矩阵的内容，大小为N*M
    for (i64 i = 0; i < N; i++) { // 遍历N行
        for (i64 j = 0; j < M; j++) { // 遍历M列
            std::cin >> maze[i][j]; // 输入每个位置上的字母
        }
    }
    i64 shortestPath = findShortestPath(maze, K); // 调用findShortestPath函数，计算最少需要多少步才能到达右下角，并赋值给shortestPath
    std::cout << shortestPath << std::endl; // 输出shortestPath
    return 0;
}