C++实现floodFill时栈引发无限循环问题求助

你的代码如下：

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
    int prevColor = image[sr][sc];
    int m = image.size();
    int n = image[0].size();
    image[sr][sc] = color;
   
    stack <pair<int, int>> positionToVisit; 
    positionToVisit.push({sr, sc});

   int t = 3000;  
    while (!positionToVisit.empty() && t--) {  //There is a problem I couldn't solve, except giving t is getting time limit error
        
        if (sr>0 && image[sr-1][sc] == prevColor ) {
            image[sr-1][sc] = color;
            positionToVisit.push({sr-1, sc});
        }
        if (sr<m-1 && image[sr+1][sc] == prevColor ) {
            image[sr+1][sc] = color;
            positionToVisit.push({sr+1, sc});
        }

        if (sc>0 && image[sr][sc-1] == prevColor ) {
            image[sr][sc-1] = color;
            positionToVisit.push({sr, sc-1});
        }
        if (sr<n-1 && image[sr][sc+1] == prevColor ) {
            image[sr][sc+1] = color;
            positionToVisit.push({sr, sc+1});
        }
        
        sr = positionToVisit.top().first;
        sc = positionToVisit.top().second;
        
        image[sr][sc] = color;
        positionToVisit.pop();

    }

    return image;
}

问题根源 #

1. 边界判断笔误：第四个判断右方的条件中，错误使用sr < n-1代替sc < n-1，导致列边界判断失效，可能错误访问越界内存，或重复压入无效节点，使栈元素持续增加。
2. 未处理原颜色与目标颜色相同的场景：当prevColor == color时，所有相同颜色的节点会被反复压入栈（因为修改后颜色仍等于prevColor），栈永远无法清空，直接触发无限循环。
3. 栈操作逻辑混乱：每次循环先基于当前sr/sc处理方向，再更新sr/sc为栈顶元素并弹出，导致节点处理顺序混乱，可能重复处理同一节点，加剧循环问题。

修复后的代码 #

vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
    int prevColor = image[sr][sc];
    // 原颜色与目标颜色一致，无需处理直接返回
    if (prevColor == color) return image;
    
    int m = image.size();
    int n = image[0].size();
    stack<pair<int, int>> positionToVisit; 
    positionToVisit.push({sr, sc});
    image[sr][sc] = color;

    while (!positionToVisit.empty()) {
        // 弹出当前要处理的节点
        auto curr = positionToVisit.top();
        positionToVisit.pop();
        int currSr = curr.first;
        int currSc = curr.second;

        // 检查上方
        if (currSr > 0 && image[currSr-1][currSc] == prevColor) {
            image[currSr-1][currSc] = color;
            positionToVisit.push({currSr-1, currSc});
        }
        // 检查下方
        if (currSr < m-1 && image[currSr+1][currSc] == prevColor) {
            image[currSr+1][currSc] = color;
            positionToVisit.push({currSr+1, currSc});
        }
        // 检查左方
        if (currSc > 0 && image[currSr][currSc-1] == prevColor) {
            image[currSr][currSc-1] = color;
            positionToVisit.push({currSr, currSc-1});
        }
        // 检查右方（修正边界判断）
        if (currSc < n-1 && image[currSr][currSc+1] == prevColor) {
            image[currSr][currSc+1] = color;
            positionToVisit.push({currSr, currSc+1});
        }
    }

    return image;
}

内容的提问来源于stack exchange，提问作者Omar Faruk Pial