CODEWITHSUNDEEP
c++algorithm
Ddorda
Ddorda

Reputation: 399

Finding boundaries of figure in 2d array

There is a figure that is represented by 1 values that are “connected” vertically, horizontally or diagonally in a 2 dementional array.
I need to save the index of the boundary of the figure (the row and column of the 0's that are connected to the figure, in any type of c++ container.

For instance, in the following 2d array, I should get the following indexes: (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

What is the most efficient way to do so, on both space and time complexity?

Upvotes: 2

Views: 701

Answers (1)

Shridhar R Kulkarni
Shridhar R Kulkarni

Reputation: 7063

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

enter image description here

enter image description here

  • If you print the matrix at the end, you'll see the boundary with 2.
  • Whatever you see as 3, if you want, you can set it back to 0.
  • isValidCoordinate() and isAnyNeighborOne() is left to you as an exercise.
  • I use vector<vector<int>> for boundary. You can try using vector<pair<int,int>> as well.
  • With the above solution you'll get inner boundary as well as outer boundary. As an exercise, you can try only inner boundary or only outer boundary.
  • You can solve the same problem with BFS as well. If the matrix is of large size, stack might overflow due to recursive calls. Better to prefer BFS in such cases.
  • Time and space complexity of the above solution is O(rows * cols).

Upvotes: 1

Related Questions