字母矩阵 - 寻找最长路径的算法

题目描述

给出一个 $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 <set>
using namespace std;

int n, m, s, t;
vector<vector<char>> matrix;
set<char> visited;

int dfs(int x, int y, int count) {
    if (x < 0 || x >= n || y < 0 || y >= m || visited.count(matrix[x][y]) != 0) {
        return count;
    }
    
    visited.insert(matrix[x][y]);
    int maxCount = count + 1;
    
    maxCount = max(maxCount, dfs(x-1, y, count+1)); // up
    maxCount = max(maxCount, dfs(x+1, y, count+1)); // down
    maxCount = max(maxCount, dfs(x, y-1, count+1)); // left
    maxCount = max(maxCount, dfs(x, y+1, count+1)); // right
    
    visited.erase(matrix[x][y]);
    
    return maxCount;
}

int main() {
    cin >> n >> m >> s >> t;
    matrix.resize(n, vector<char>(m));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> matrix[i][j];
        }
    }
    
    int maxCount = dfs(s-1, t-1, 0);
    cout << maxCount << endl;
    
    return 0;
}