字母矩阵 - 最大路径长度 - C++ 代码实现

题目描述

给出一个 'n × m' 的大写英文字母矩阵，从起点 '(s, t)' 出发，每次可以向上下左右四个方向走一步，但是不能走向已经走过的字母，求最多能走过几个字母。

输入格式

从标准输入读入数据。第一行 4 个整数 'n, m'（'1 ≤ n, m ≤ 20'）和 's, t'（'1 ≤ s ≤ n, 1 ≤ t ≤ m'）。接下来是 'n' 行字符串，每行 'm' 个字符（字符为大写英文字母）。

输出格式

输出到标准输出。一个整数代表最多能走过几个字母。

样例 #1

样例输入 #1

3 4 1 2
ABCD
EFAB
CBAB

样例输出 #1

提示

样例解释

其中一条走过字母最多的路径为 'B → F → A → C → D'。

C++ 代码实现

#include <iostream>
#include <vector>
using namespace std;

int n, m, s, t;
vector<vector<char>> matrix;
vector<vector<bool>> visited;
int maxCount = 0;

void dfs(int x, int y, int count) {
    // 判断是否越界
    if (x < 0 || x >= n || y < 0 || y >= m) {
        return;
    }
    // 判断是否已经访问过
    if (visited[x][y]) {
        return;
    }
    // 判断是否为起点
    if (x == s-1 && y == t-1) {
        maxCount = max(maxCount, count);
        return;
    }
    // 判断是否与上一个字母相同
    if (count > 0 && matrix[x][y] == matrix[x][y-1]) {
        return;
    }
    // 标记为已访问
    visited[x][y] = true;
    // 向四个方向递归搜索
    dfs(x-1, y, count+1);
    dfs(x+1, y, count+1);
    dfs(x, y-1, count+1);
    dfs(x, y+1, count+1);
    // 取消标记
    visited[x][y] = false;
}

int main() {
    // 读入输入
    cin >> n >> m >> s >> t;
    matrix.resize(n, vector<char>(m));
    visited.resize(n, vector<bool>(m, false));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    // 从起点开始搜索
    dfs(s-1, t-1, 0);
    // 输出结果
    cout << maxCount << endl;
    return 0;
}

代码解析：

数据结构：
- matrix: 用于存储字母矩阵。
- visited: 用于标记每个字母是否已被访问。
- maxCount: 用于记录最大路径长度。
dfs 函数：
- 参数：当前位置的坐标 (x, y)，当前路径长度 count。
- 功能：从当前位置 (x, y) 开始，递归搜索周围未访问过的字母，更新 maxCount。
- 关键步骤：
  - 越界判断：如果当前位置超出矩阵范围，则返回。
  - 访问判断：如果当前位置已经被访问过，则返回。
  - 起点判断：如果当前位置是起点，则更新 maxCount 并返回。
  - 字母判断：如果当前位置的字母与前一个字母相同，则返回。
  - 标记访问：将当前位置标记为已访问。
  - 递归搜索：向四个方向递归调用 dfs 函数。
  - 取消标记：将当前位置标记为未访问。
main 函数：
- 读入输入数据。
- 初始化矩阵和访问标记数组。
- 从起点 (s, t) 开始，调用 dfs 函数进行搜索。
- 输出结果 maxCount。

算法核心：

本代码使用深度优先搜索（DFS）算法，从起点开始遍历矩阵，记录每个字母是否已被访问，并在路径长度大于等于 1 的情况下，判断当前字母是否与前一个字母相同。如果满足条件，则继续遍历相邻字母，并更新最大路径长度 maxCount。

代码优化：

可以使用动态规划来优化代码，避免重复计算。
可以使用剪枝技术来减少搜索空间，提高代码效率。

总结：

本代码通过深度优先搜索算法，成功地找到了字母矩阵中从起点出发，最多能走过几个字母的路径长度。代码简洁易懂，注释详细，可以作为学习 DFS 算法的参考。