带障碍物的二维网格中通信塔互达性检测方案咨询

咱们一步步拆解这个问题哈——因为涉及网格移动、障碍物阻挡，还要判断通信塔之间的双向覆盖，得用一套能处理所有边界情况（比如被障碍物挡住的路径）的系统方法。先明确几个核心定义避免理解偏差：

• 通信塔编号：按从上到下、每行从左到右的顺序给所有T单元格编号，比如左上角第一个T是1，下一个同列下方或同行右侧的T是2，以此类推。
• 覆盖范围：从某塔出发，沿上/下/左/右四方向移动，最多走D步（每步一格），且路径上不能穿过#障碍物，所有能到达的单元格（包括塔自身）都属于该塔的覆盖范围。这里的“D个单元格”指的是移动步数不超过D，比如D=3时，最多能走到距离塔3步的位置（中间无阻挡的话）。

1. 先定位所有通信塔的位置并编号 #

首先得遍历整个网格，把所有T的坐标按顺序记下来，同时给它们分配编号。比如用一个数组存每个塔的坐标，数组索引+1就是塔的编号（方便后续对应）。

举个C++的例子：

vector<pair<int, int>> tower_pos; // 索引0对应塔1，索引1对应塔2...
int rows = grid.size();
int cols = grid[0].size();

for (int i = 0; i < rows; ++i) {
    for (int j = 0; j < cols; ++j) {
        if (grid[i][j] == 'T') {
            tower_pos.emplace_back(i, j);
        }
    }
}

2. 用BFS计算每个塔的覆盖范围 #

这一步是关键！因为障碍物会阻挡路径，不能直接用曼哈顿距离瞎判断，必须用**广度优先搜索（BFS）**来计算每个塔能到达的所有单元格——BFS天生适合处理这种无权重网格的最短路径问题，能准确找出所有步数≤D且无障碍物阻挡的可达位置。

具体流程：

• 建一个和网格一样大的距离矩阵dist，初始值全设为-1（表示不可达）。
• 把当前塔的坐标放进队列，设置它的距离为0（自身步数为0）。
• 从队列里取出单元格，遍历四个方向的相邻单元格：
  • 如果相邻单元格在网格范围内、不是障碍物、且还没被访问过（dist为-1），就把它的距离设为当前单元格的步数+1。
  • 如果这个新步数≤D，就把它加入队列继续探索；超过D的话就不用管了，因为已经超出覆盖范围。
• 遍历结束后，dist矩阵里所有值≤D的位置，就是这个塔的覆盖范围。

示例代码片段：

vector<vector<int>> calc_coverage(int start_r, int start_c, const vector<vector<char>>& grid, int D) {
    int rows = grid.size();
    int cols = grid[0].size();
    vector<vector<int>> dist(rows, vector<int>(cols, -1));
    queue<pair<int, int>> q;
    // 四个移动方向：上、右、下、左
    vector<pair<int, int>> dirs = {{-1,0}, {0,1}, {1,0}, {0,-1}};

    dist[start_r][start_c] = 0;
    q.emplace(start_r, start_c);

    while (!q.empty()) {
        auto [r, c] = q.front();
        q.pop();

        for (auto [dr, dc] : dirs) {
            int nr = r + dr;
            int nc = c + dc;
            // 检查是否在网格内、不是障碍物、未被访问过
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                if (grid[nr][nc] != '#' && dist[nr][nc] == -1) {
                    dist[nr][nc] = dist[r][c] + 1;
                    if (dist[nr][nc] <= D) {
                        q.emplace(nr, nc);
                    }
                }
            }
        }
    }
    return dist;
}

3. 两两判断塔的双向覆盖关系 #

现在我们已经有了每个塔的覆盖范围矩阵，接下来只需要遍历所有塔的两两组合（避免重复判断，比如只看i<j的组合），检查两个条件：

• 塔A的覆盖范围是否包含塔B（即塔B的坐标在A的dist矩阵中值≤D）
• 塔B的覆盖范围是否包含塔A（即塔A的坐标在B的dist矩阵中值≤D）
  如果两个条件都满足，就说明这对塔彼此处于对方的覆盖范围内。

示例逻辑：

int tower_num = tower_pos.size();
vector<pair<int, int>> mutual_pairs; // 存彼此覆盖的塔编号对

// 先预计算所有塔的覆盖矩阵
vector<vector<vector<int>>> all_coverages;
for (auto [r, c] : tower_pos) {
    all_coverages.push_back(calc_coverage(r, c, grid, D));
}

// 遍历所有两两组合
for (int i = 0; i < tower_num; ++i) {
    for (int j = i + 1; j < tower_num; ++j) {
        // 塔i+1是否覆盖塔j+1？
        bool a_covers_b = (all_coverages[i][tower_pos[j].first][tower_pos[j].second] != -1 
                           && all_coverages[i][tower_pos[j].first][tower_pos[j].second] <= D);
        // 塔j+1是否覆盖塔i+1？
        bool b_covers_a = (all_coverages[j][tower_pos[i].first][tower_pos[i].second] != -1 
                           && all_coverages[j][tower_pos[i].first][tower_pos[i].second] <= D);
        
        if (a_covers_b && b_covers_a) {
            mutual_pairs.emplace_back(i+1, j+1); // 编号从1开始
        }
    }
}

几个容易踩坑的点 #

• 别用曼哈顿距离代替BFS：两个塔的曼哈顿距离可能小于D，但中间有障碍物挡着，实际需要绕路，步数可能超过D，这时候就不算覆盖。
• BFS要及时终止：当步数超过D时，就别再往队列里加这个方向的单元格了，能省不少计算时间。
• 重复计算优化：如果只是要判断两两覆盖，也可以在计算塔A的覆盖范围时直接检查所有其他塔是否在范围内，之后计算塔B时只需要反向验证，但预存所有覆盖矩阵会更清晰，方便后续扩展功能。

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