DFS写法 C++ 代码

#include <bits/stdc++.h>
using namespace std;

int R, S;
int maxCount = 0; // 记录最大不同字母数量

// DFS 函数
void DFS(vector<vector<char>> &matrix, vector<vector<bool>> &visited, set<char> &uniqueChars, int x, int y) {
    // 越界检查
    if (x < 0 || x >= R || y < 0 || y >= S) 
        return;

    // 如果当前字母已经访问过，直接返回
    if (visited[x][y] || uniqueChars.count(matrix[x][y])) 
        return;

    // 标记当前节点为已访问
    visited[x][y] = true;
    uniqueChars.insert(matrix[x][y]); // 将当前字母加入集合

    // 更新最大不同字母数量
    maxCount = max(maxCount, (int)uniqueChars.size());

    // 递归访问四个方向
    DFS(matrix, visited, uniqueChars, x, y-1); // 上
    DFS(matrix, visited, uniqueChars, x, y+1); // 下
    DFS(matrix, visited, uniqueChars, x+1, y); // 右
    DFS(matrix, visited, uniqueChars, x-1, y); // 左

    // 回溯：移除当前字母并取消访问标记
    uniqueChars.erase(matrix[x][y]);
    visited[x][y] = false;
}

int main() {
    cin >> R >> S;
    vector<vector<char>> matrix(R, vector<char>(S));
    vector<vector<bool>> visited(R, vector<bool>(S, false)); // 记录节点是否被访问过

    // 读入矩阵
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < S; j++) {
            cin >> matrix[i][j];
        }
    }

    set<char> uniqueChars; // 记录当前路径中的不同字母
    DFS(matrix, visited, uniqueChars, 0, 0); // 从起点 (0, 0) 开始 DFS

    // 输出结果
    cout << maxCount;

    return 0;
}