Finden von Grenzen der Figur in 2d Array

Question

Es gibt eine Zahl, die durch 1 Werte dargestellt wird, die vertikal, horizontal oder diagonal in einem 2-Demenz-Array „verbunden“ sind.
Ich muss den Index der Grenze der Figur (die Zeile und Spalte der Nullen, die mit der Figur verbunden sind, in jeder Art von C ++ - Container speichern.

Zum Beispiel sollte ich im folgenden 2d-Array die folgenden Indizes erhalten: (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

Was ist der effizienteste Weg, um die räumliche und zeitliche Komplexität zu verbessern?

Answer 1

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;
}

• Wenn Sie die Matrix am Ende drucken, sehen Sie die Grenze mit 2.
• Was auch immer Sie sehen 3, wenn Sie möchten, können Sie es zurücksetzen 0.
• isValidCoordinate()und isAnyNeighborOne()bleibt dir als Übung überlassen.
• Ich benutze vector<vector<int>>für die Grenze. Sie können es auch versuchen vector<pair<int,int>>.
• Mit der obigen Lösung erhalten Sie sowohl die innere als auch die äußere Grenze. Als Übung können Sie nur die innere Grenze oder nur die äußere Grenze ausprobieren.
• Sie können das gleiche Problem auch mit BFS lösen. Wenn die Matrix groß ist, kann der Stapel aufgrund rekursiver Aufrufe überlaufen. In solchen Fällen ist es besser, BFS zu bevorzugen.
• Zeitliche und räumliche Komplexität der obigen Lösung ist O(rows * cols).