查找二维数组中图形的边界

有一个图形由 1 个值表示，这些值在 2 维数组中垂直、水平或对角线“连接”。
我需要在任何类型的 C++ 容器中保存图形边界的索引（连接到图形的 0 的行和列）。

例如，在下面的二维数组中，我应该获得以下索引：(0,2), (0,3), (0,4), (1,2), (1,4), (1,5), (2,2), (2,3), (2,5), (2,6)... etc.

0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 1 1 0 0
0 0 0 0 1 1 0 0
0 0 0 1 1 1 0 0
0 0 0 1 1 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

在空间和时间复杂度上，最有效的方法是什么？

void dfs(vector<vector<int>>& matrix, vector<vector<int>>& boundary, int rows, int cols, int i, int j){
    if(!isValidCoordinate(i, j))
        return;
    
    if(isAnyNeighborOne(i, j)){
        boundary.push_back({i, j});
        matrix[i][j] = 2;
    }
    else
        matrix[i][j] = 3;

    //Explore eight directions
    /* I didn't bother about x = 0 and y = 0. 
     * You can, if you want.
     * Doesn't make a difference though. 
     */
    for(int x = -1; x < 2; x++){
        for(int y = -1; y < 2; y++){
            dfs(matrix, boundary, rows, cols, i + x, i + y);
        }
    }
}

vector<vector<int>> getBoundary(vector<vector<int>>& matrix){
    vector<vector<int>> boundary;
    int rows = matrix.size();
    if(!rows)
        return boundary;
    int cols = matrix[0].size();
    for(int i = 0; i < rows; i++){
        for(int j = 0; j < cols; j++){
            if(matrix[i][j] == 0){
                dfs(matrix, boundary, rows, cols, i, j);
            }
        }
    }
    return boundary;
}

• 如果在最后打印矩阵，您将看到边界2.
• 无论你看到什么3，如果你愿意，你可以将其设置回0.
• isValidCoordinate() and isAnyNeighborOne()留给你作为练习。
• I use vector<vector<int>>为边界。您可以尝试使用vector<pair<int,int>>以及。
• 通过上述解决方案，您将获得内部边界和外部边界。作为练习，您可以仅尝试内部边界或仅尝试外部边界。
• 您也可以使用 BFS 解决同样的问题。如果矩阵很大，堆栈可能会因递归调用而溢出。在这种情况下最好选择 BFS。
• 上述解的时间和空间复杂度为O(rows * cols).