移除代码中植物位置输入注释后程序超时，求问题排查

首先，咱们先拆解你移除读取植物位置代码后超时的直接原因：

• 当你注释掉读取K个植物位置的循环后，vec网格被初始化为全0（vector<vector<int>> vec(n, vector<int>(m,0));）。接下来那段寻找第一个值为1的单元格的双重循环：

  for(i=0;i<n;i++) {
    for(j=0;j<m;j++) {
      if(vec[i][j] == 1) {
        q.push(make_pair(i,j));
        flag = 1;
        break;
      }
    }
    if(flag==1) break;
  }
  

  会完整遍历整个N×M的网格——因为网格里根本没有值为1的单元格。如果N和M的规模较大（比如1000×1000就是100万次循环，更大的话比如1e4×1e4就是1亿次），这必然会触发超时。

但这还不是唯一的问题，你的代码本身还有几个致命逻辑错误，即使恢复读取植物的代码，也会导致错误或者超时：

1. BFS中的多余循环导致重复操作甚至死循环 #

在BFS处理部分，你写了完全多余的内层循环：

for(i=0;i<4;i++) {
  for(j=0;j<4;j++) { // 这层循环完全没必要！
    int rr = a + r[i];
    int cc = b + c[j];
    // ... 后续判断
  }
}

r和c数组已经对应了上下左右四个方向的偏移量，只需要循环一次i从0到3就能遍历所有方向。现在的写法会把每个方向重复处理4次，导致同一个相邻单元格被多次加入队列，不仅大幅增加计算量，还会因为没有标记已访问单元格，出现死循环（同一个单元格被反复入队、处理）。

2. 未标记已访问单元格 #

你的BFS没有标记已经处理过的植物单元格，这会导致同一个单元格被多次加入队列，重复计算，进一步加剧超时问题。比如单元格A的相邻单元格B被处理时，又会把A重新加入队列，无限循环。

修复后的完整代码示例 #

这里给你修复后的代码，解决了上述所有问题：

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

int main() {
    int t;
    // 四个方向的偏移量
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        vector<vector<int>> grid(n, vector<int>(m, 0));
        vector<vector<bool>> visited(n, vector<bool>(m, false)); // 标记已访问
        queue<pair<int, int>> q;

        // 读取植物位置并初始化队列和访问标记
        for (int z = 0; z < k; z++) {
            int r, c;
            cin >> r >> c;
            r--; c--; // 转换为0-based索引
            grid[r][c] = 1;
            q.push({r, c});
            visited[r][c] = true;
        }

        int ans = 0;
        while (!q.empty()) {
            auto curr = q.front();
            q.pop();
            int x = curr.first;
            int y = curr.second;
            int adjacent_plants = 0;

            // 遍历四个方向
            for (int i = 0; i < 4; i++) {
                int nx = x + dr[i];
                int ny = y + dc[i];
                // 检查是否在网格内且为未访问的植物
                if (nx >= 0 && nx < n && ny >=0 && ny < m) {
                    if (grid[nx][ny] == 1) {
                        adjacent_plants++;
                        if (!visited[nx][ny]) {
                            visited[nx][ny] = true;
                            q.push({nx, ny});
                        }
                    }
                }
            }
            ans += (4 - adjacent_plants);
        }
        cout << ans << endl;
    }
    return 0;
}

关键修复点说明 #

• 移除了BFS中多余的内层循环，只遍历四个方向一次，避免重复计算。
• 添加了visited二维数组，标记已处理的植物单元格，彻底解决重复入队和死循环问题。
• 提前将植物位置加入队列并标记为已访问，省去了后续遍历整个网格寻找第一个植物的步骤，大幅提升效率。
• 优化了变量命名，让代码逻辑更清晰易懂。

现在即使你不小心再次注释掉读取植物的代码，程序也会因为队列为空直接输出0，不会遍历整个网格，也就不会超时了。

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