C++二维Vector地图验证：城镇厅尺寸与间距合规性实现问询

嘿，我明白你不想写一堆嵌套if的痛苦——这种网格验证问题确实可以用更结构化、更简洁的方式来实现，不用靠堆条件判断。让我给你梳理一个清晰的C++方案，完全贴合你提到的规则：

先明确规则细节 #

先把你提到的规则再明确一下，避免歧义：

• 城镇厅是由连续的T组成的矩形区域，尺寸范围是1x1到3x3（比如3x3的厅就是9个连续的T组成的正方形）
• 地图中至少存在1个城镇厅
• 任意两个城镇厅之间不能相邻（包括斜向相邻，也就是两个厅的格子不能共享任何边或角）

核心实现思路 #

我们可以用「标记已访问区域 + 边界提取 + 范围检查」的思路，替代大量的if判断：

1. 用一个二维布尔数组标记已经处理过的T格子，避免重复检查
2. 遍历地图中的每个格子，遇到未访问的T时，提取整个城镇厅的边界（最小/最大行、列）
3. 验证该城镇厅的尺寸是否在1x1~3x3范围内，同时确认边界内的所有格子都是T（确保是矩形的连续区域）
4. 检查该城镇厅的扩展边界（周围一圈，包括斜向）内是否存在未访问的T——如果有，说明两个厅相邻，验证失败
5. 最后确保至少找到一个城镇厅

C++代码实现 #

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>

using namespace std;

// 验证地图是否符合规则
bool validateMap(const vector<string>& map) {
    if (map.empty()) return false;
    int rows = map.size();
    int cols = map[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    int hallCount = 0;

    // 遍历每个格子
    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (map[i][j] == 'T' && !visited[i][j]) {
                hallCount++;
                // 提取当前城镇厅的边界
                int minRow = i, maxRow = i;
                int minCol = j, maxCol = j;

                // 找同一列上下的所有T，确定行边界
                for (int r = 0; r < rows; ++r) {
                    if (map[r][j] == 'T') {
                        minRow = min(minRow, r);
                        maxRow = max(maxRow, r);
                    }
                }
                // 找同一行左右的所有T，确定列边界
                for (int c = 0; c < cols; ++c) {
                    if (map[i][c] == 'T') {
                        minCol = min(minCol, c);
                        maxCol = max(maxCol, c);
                    }
                }

                // 验证城镇厅尺寸：1x1 ~ 3x3
                int height = maxRow - minRow + 1;
                int width = maxCol - minCol + 1;
                if (height < 1 || height > 3 || width < 1 || width > 3) {
                    return false;
                }

                // 验证边界内的所有格子都是T（确保是完整的矩形城镇厅）
                for (int r = minRow; r <= maxRow; ++r) {
                    for (int c = minCol; c <= maxCol; ++c) {
                        if (map[r][c] != 'T') {
                            return false;
                        }
                        visited[r][c] = true; // 标记为已访问
                    }
                }

                // 检查周围扩展区域是否有未访问的T（相邻的其他城镇厅）
                int startRow = max(0, minRow - 1);
                int endRow = min(rows - 1, maxRow + 1);
                int startCol = max(0, minCol - 1);
                int endCol = min(cols - 1, maxCol + 1);

                for (int r = startRow; r <= endRow; ++r) {
                    for (int c = startCol; c <= endCol; ++c) {
                        // 跳过当前城镇厅的区域
                        if (r >= minRow && r <= maxRow && c >= minCol && c <= maxCol) {
                            continue;
                        }
                        if (map[r][c] == 'T' && !visited[r][c]) {
                            // 发现相邻的未处理T，说明两个厅相邻
                            return false;
                        }
                    }
                }
            }
        }
    }

    // 至少有一个城镇厅
    return hallCount >= 1;
}

// 测试示例
int main() {
    vector<string> validMap = {
        "GGGGGGGTGGG",
        "GGTTTGGGGT",
        "GGTTTGGGGT",
        "GGTTTGGGGT",
        "GGGGGGTTGG"
    };
    vector<string> invalidMap = {
        "GGGGGGGGGG",
        "GGTTTTGGGT",
        "GGTTTGGGGT",
        "GGTTTGGGTT",
        "GGGGTTGGGG"
    };

    cout << "Valid map check: " << (validateMap(validMap) ? "Pass" : "Fail") << endl;
    cout << "Invalid map check: " << (validateMap(invalidMap) ? "Pass" : "Fail") << endl;
    return 0;
}

关键细节解释 #

• 边界提取：没有用复杂的连通性遍历（比如BFS），而是利用城镇厅是矩形的特性，直接找同一列的上下边界和同一行的左右边界，代码更简洁
• 尺寸验证：通过计算高度和宽度，直接判断是否在1-3范围内，替代了一堆if (height ==1 || height ==2 || height ==3)这种冗余判断
• 相邻检查：通过扩展边界（当前厅的上下左右各加一行/列），遍历这个区域内的格子，跳过当前厅的区域后，只要发现未访问的T，就说明有相邻的其他厅，直接返回false
• 已访问标记：确保每个T只被处理一次，避免重复检查和错误判断

这样的实现几乎没有嵌套的if判断，逻辑清晰，而且容易扩展（比如以后要修改城镇厅尺寸范围，只需要改数字就行）。

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