字母矩阵 - 最大路径长度

题目描述

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

3 4 1 2
ABCD
EFAB
CBAB

样例输出 #1

5

提示

样例解释

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

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
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) {
    visited[x][y] = true;
    maxCount = max(maxCount, count);
    if (x > 0 && !visited[x - 1][y] && matrix[x - 1][y] != matrix[x][y]) {
        dfs(x - 1, y, count + 1);
    }
    if (x < n - 1 && !visited[x + 1][y] && matrix[x + 1][y] != matrix[x][y]) {
        dfs(x + 1, y, count + 1);
    }
    if (y > 0 && !visited[x][y - 1] && matrix[x][y - 1] != matrix[x][y]) {
        dfs(x, y - 1, count + 1);
    }
    if (y < m - 1 && !visited[x][y + 1] && matrix[x][y + 1] != matrix[x][y]) {
        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, 1);
    cout << maxCount << endl;
    return 0;
}