C++递归实现二维字符串同字符连通区域面积计算求助

我看了你写的代码，思路方向是对的，但几个关键逻辑出错导致无法正确统计所有连通区域，咱们一步步来修正：

现有代码的核心问题 #

• 坐标转换错误：cords函数的索引计算没考虑换行符的占位，导致二维坐标和字符串索引完全对应不上
• 递归逻辑残缺：只处理了向右、向下两个方向，漏掉了左、上，而且用x++这种后置递参会导致传递错误的坐标值，递归路径直接走偏
• 无访问标记：没有记录已统计的字符，会重复计算或者漏算连通区域
• 硬编码边界：直接写死x>32 || y>6，不够灵活，也无法适配不同输入

修正方案与完整代码 #

1. 先搞定正确的坐标转换 #

改用0-based坐标（行y从0到5，列x从0到31），每行包含32个有效字符+1个换行符，所以字符串索引公式为：y * (每行有效字符数 + 1) + x，这样能准确对应每个二维位置。

2. 添加访问标记数组 #

创建一个和二维字符串对应的布尔数组visited，初始全为false，访问过的位置标记为true，避免重复统计。

3. 重写递归逻辑 #

递归需要处理当前位置的上下左右四个相邻方向，每个位置需满足：坐标合法、字符匹配、未被访问。

完整修正代码 #

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

// 0-based坐标转字符串索引
int getIndex(const string& str, int x, int y, int colsPerLine) {
    // 每行长度=有效字符数+1（包含换行符）
    return y * (colsPerLine + 1) + x;
}

// 递归计算连通区域面积
int clusterMiner(const string& str, int x, int y, int colsPerLine, int rows, 
                 vector<vector<bool>>& visited, char target) {
    // 边界/合法性检查：越界、已访问、字符不匹配则返回0
    if (x < 0 || x >= colsPerLine || y < 0 || y >= rows || 
        visited[y][x] || str[getIndex(str, x, y, colsPerLine)] != target) {
        return 0;
    }

    // 标记当前位置为已访问
    visited[y][x] = true;
    int area = 1; // 当前字符占1个面积单位

    // 递归遍历上下左右四个方向
    area += clusterMiner(str, x + 1, y, colsPerLine, rows, visited, target); // 右
    area += clusterMiner(str, x - 1, y, colsPerLine, rows, visited, target); // 左
    area += clusterMiner(str, x, y + 1, colsPerLine, rows, visited, target); // 下
    area += clusterMiner(str, x, y - 1, colsPerLine, rows, visited, target); // 上

    return area;
}

int main() {
    string text = 
        "#################aa##a###c######\n"
        "####bbbbaaaabbbbbaaaaa###ccc##cc\n"
        "#o##bbbbaaaabbbbbaaaaa###c#c##cc\n"
        "#oo#bbbbaeeabbbbbbbbaa##cc#ccccc\n"
        "#o##bbbbaeeabbbbbaaaaaa#cc#####c\n"
        "#o##bbbbaaaabbbbbaaaaaa#cc#####c\n";

    // 动态统计行数和每行有效字符数
    int rows = 0;
    int colsPerLine = 0;
    bool firstLine = true;
    for (char c : text) {
        if (c == '\n') {
            rows++;
            firstLine = false;
        } else if (firstLine) {
            colsPerLine++;
        }
    }

    // 初始化访问标记数组
    vector<vector<bool>> visited(rows, vector<bool>(colsPerLine, false));

    // 按行扫描所有字符，启动递归统计
    for (int y = 0; y < rows; y++) {
        for (int x = 0; x < colsPerLine; x++) {
            if (!visited[y][x]) {
                char currentChar = text[getIndex(text, x, y, colsPerLine)];
                int area = clusterMiner(text, x, y, colsPerLine, rows, visited, currentChar);
                cout << "字符 '" << currentChar << "' 的连通区域面积：" << area << endl;
            }
        }
    }

    return 0;
}

代码说明 #

• 坐标转换：getIndex函数准确计算每个二维位置对应的字符串索引，解决了换行符的干扰问题
• 访问标记：visited数组确保每个字符只被统计一次，避免重复计算同一个连通区域
• 递归逻辑：覆盖四个方向的相邻位置，完整遍历整个连通区域
• 动态行列计算：从输入字符串自动统计行列数，代码适配性更强

运行这段代码后，就能正确输出所有连通区域的字符和对应面积了。

内容的提问来源于stack exchange，提问作者Max Twardowski