广度优先搜索（BFS）

解释用例

棋盘最大涂色区域：有一个 n x m 的棋盘，每个格子涂有不同颜色。需要找到其中同一颜色面积最大的连续区域（按照四连通标准），并求出其面积。

第一行 2 个正整数 n,m，描述棋盘尺寸。
接下来 n 行描述这个棋盘，每行 m 个字符，每个字符为 W（白）/G（绿）/R（红）/B（蓝），表示对应格子的颜色。

算法实现

1、加载棋盘数据（LoadChessboard）

• 函数介绍：该函数的作用是从文件中读取棋盘的行列数据和相应的棋盘内容。

流程：

• 使用 std::ifstream 来打开指定路径的文件。
• 检查文件是否成功打开，如果没有则返回 false。
• 读取行数 rows 和列数 cols。
• 将 chessboard 初始化为 rows x cols 的二维字符向量。
• 使用嵌套循环读取每一个位置的字符（代表颜色），填入 chessboard 中。
• 完成后关闭文件并返回 true。

代码：

bool loadChessboard(const std::string& filePath) {
    // ifstream文件打开文件
    std::ifstream inputFile(filePath);
    if (!inputFile.is_open()) {
        return false;
    }
    
    // 读取行列并根据行列设置数组
    inputFile >> rows >> cols;
    chessboard.resize(rows, std::vector<char>(cols));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            inputFile >> chessboard[i][j];
        }
    }
    
    inputFile.close();
    return true;
}

2. 广度优先搜索算法 (bfs)

• 函数介绍：这个函数使用 BFS 算法来计算一个特定颜色区域的面积，并返回面积和颜色。

流程：

• 创建一个队列 q 来存储当前正在处理的棋盘点。
• 将起始坐标（startX，startY）压入队列，并标记为已访问。
• 记录起始点的颜色。
• 定义两个数组 dx 和 dy，分别表示四个方向的变化量（上、下、左、右）。
• 进入 while 循环直到队列为空：
  • 从队列中弹出一个点，增加区域面积计数 area。
  • 遍历四个方向，计算新坐标 nx 和 ny。
  • 使用 isValid 函数检查新坐标的有效性，并且如果新坐标的颜色与当前颜色相同，则将其标记为访问过并压入队列。
• 返回最终计算得到的区域面积和颜色。

代码：

// 返回两个类型的值，使用pair
std::pair<int, char> bfs(int startX, int startY, std::vector<std::vector<bool>>& visited) {
    // 队列存储点
    std::queue<std::pair<int, int>> q;
    // 将起始坐标压入队列，并标记为已访问
    q.push({ startX, startY });
    visited[startX][startY] = true;
    
    char color = chessboard[startX][startY]; // 记录颜色
    
    // 用数组dx和dy来表示四个方向的变化量（上下左右）
    const int dx[4] = { -1, 1, 0, 0 };
    const int dy[4] = { 0, 0, -1, 1 };
    
    int area = 0;
    while (!q.empty()) {
        // 从队列中弹出一个点，增加area
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        area++;

        // 遍历四个方向的新点，在判断点的有效性后，如果新遍历的点的颜色与原点相同，则压入队列
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isValid(nx, ny, visited) && chessboard[nx][ny] == color) {
                visited[nx][ny] = true;
                q.push({ nx, ny });
            }
        }
    }
    
    return { area, color };
}

3. 检查点的有效性 (isValid)

• 函数介绍：此函数用于验证一个点在棋盘上的有效性，确保点在棋盘范围内且未被访问。

流程：

• 检查 x 和 y 是否在有效范围内（大于等于0且小于行数和列数）。
• 检查 visited[x][y] 是否为 false（表示该点未被访问）。
• 只有满足以上条件，函数才返回 true，其他情况返回 false。

代码：

// 检查点是否有效
bool ChessAnalyzer::isValid(int x, int y, std::vector<std::vector<bool>>& visited) {
    return x >= 0 && x < rows&& y >= 0 && y < cols && !visited[x][y];
}

4. 计算最大面积 (calculateMaxArea)

• 函数介绍：该函数遍历整个棋盘以寻找具有最大面积的颜色区域。

流程：

• 首先检查棋盘是否为空，如果为空，则返回面积为0及颜色为 '\0'。
• 初始化一个 visited 数组，用于标记访问过的点。
• 初始化 maxArea 和 maxColor 变量来存储当前最大面积及其对应的颜色。
• 使用双重循环遍历棋盘的每个位置：
  • 如果该点未被访问，调用 bfs 函数来计算该颜色区域的面积及颜色。
  • 如果返回的面积大于当前最大面积，则更新 maxArea 和 maxColor。
• 最终返回找到的最大区域面积及其颜色。

代码：

// 计算最大面积
std::pair<int, char> ChessAnalyzer::calculateMaxArea() {
    if (chessboard.empty()) return { 0, '\0' };
    
    // 访问棋盘
    std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
    int maxArea = 0;
    char maxColor = '\0';
    
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (!visited[i][j]) {
                auto result = bfs(i, j, visited); // 调用 bfs 返回面积和颜色
                int area = result.first;
                char color = result.second;
                
                if (area > maxArea) {
                    maxArea = area;
                    maxColor = color;
                }
            }
        }
    }
    
    return { maxArea, maxColor }; // 返回最大面积和对应的颜色
}

完整代码

// 读取棋盘数据
bool loadChessboard(const std::string& filePath) {
    std::ifstream inputFile(filePath);
    if (!inputFile.is_open()) {
        return false;
    }
    
    // 读取行列并根据行列设置数组
    inputFile >> rows >> cols;
    chessboard.resize(rows, std::vector<char>(cols));
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            inputFile >> chessboard[i][j];
        }
    }
    
    inputFile.close();
    return true;
}

// bfs
std::pair<int, char> bfs(int startX, int startY, std::vector<std::vector<bool>>& visited) {
    // 队列存储点
    std::queue<std::pair<int, int>> q;
    // 将起始坐标压入队列，并标记为已访问
    q.push({ startX, startY });
    visited[startX][startY] = true;
    
    char color = chessboard[startX][startY]; // 记录颜色
    
    // 用数组dx和dy来表示四个方向的变化量（上下左右）
    const int dx[4] = { -1, 1, 0, 0 };
    const int dy[4] = { 0, 0, -1, 1 };
    
    int area = 0;
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        area++;
        
        // 遍历四个方向的新点，在判断点的有效性后，如果新遍历的点的颜色与原点相同，则压入队列
        for (int i = 0; i < 4; ++i) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (isValid(nx, ny, visited) && chessboard[nx][ny] == color) {
                visited[nx][ny] = true;
                q.push({ nx, ny });
            }
        }
    }

    return { area, color };
}

// 检查点是否有效
bool isValid(int x, int y, std::vector<std::vector<bool>>& visited) {
    return x >= 0 && x < rows&& y >= 0 && y < cols && !visited[x][y];
}

// 计算最大面积
std::pair<int, char> ChessAnalyzer::calculateMaxArea() {
    if (chessboard.empty()) return { 0, '\0' };
    
    // 访问棋盘
    std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
    int maxArea = 0;
    char maxColor = '\0';
    
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (!visited[i][j]) {
                auto result = bfs(i, j, visited); // 调用 bfs 返回面积和颜色
                int area = result.first;
                char color = result.second;
                
                if (area > maxArea) {
                    maxArea = area;
                    maxColor = color;
                }
            }
        }
    }

    return { maxArea, maxColor }; // 返回最大面积和对应的颜色
}