CODEWITHSUNDEEP
algorithm
Richard
Richard

Reputation: 7433

Finding the existence of an enclosed space within a 2D M x N grid

I'm tasked to find an the existence of an enclosed space within a grid provided by the questions using an algorithm. A space (' ') means that there is a hole while a hash ('#') means that there is a wall. Now suppose I have a two-dimensional M x N grid, how do I find if there's an existence of enclosed space? Examples of grid with enclosed space(s):

########
#      #
#      #
#      #
#      #
#      #
#      #
########

########
#      #
#      #
########
#      #
#      #
#       
########

########
# #    #
# #    #
# ######
#      #
#      #
#       
########

########
##     #
# #    #
#  #   #
#   #  #
#    # 
#     # 
########

At first, I tried to store this grid into a vector of strings. Then, I proceeded to check if each space is a hash or a space. If it's a space (its position will now be called as initial), I would check the surrounding areas of that space until I find a hole (space) that is reachable on the edges from said initial. If it's a hash, I'd continue with the next 'square' in the grid.

However, my algorithm of trying to just brute force every single possibility seems very tedious and inefficient. Should I learn about some other concepts before proceeding with this task (reading more about maps, paths, trees, etc.). If there is, could you please provide me what to read first? If there isn't, could you please guide me?

And is my approach to solving this task correct?

Upvotes: 1

Views: 1870

Answers (1)

Shudipta Sharma
Shudipta Sharma

Reputation: 5872

The idea is:

  • we start from every non-visited empty cell
  • try to visit all connected empty cells
  • if we can go to the boundary then this is not an enclosed area
  • if no cell of the connected region is boundary cell then the region is enclosed by wall and we increment the count.

Here is sample implementation in c++ that count the number of enclosed area:

#include <string.h>
#include <cstdio>

// m is row_num, n is column_num
int m, n;
// grid
char grid[5005][5005];
// direction arrays
int R[] = {0, -1, 0, 1};
int C[] = {1, 0, -1, 0};
// check for weather we reach boundary or not
// and visit array
bool wentToBoundary, vis[5005][5005];

// DFS implementation of 2D grid
void dfs(int x, int y) {
    // visit the cell grid[x][y] as true
    vis[x][y] = true;

    // if the current cell is a boundary cell, then mark that
    // we reach to boundary from an inner cell
    if (x == 0 || x == m -1 || y == 0 || y == n - 1)
        wentToBoundary = true;

    // try to go in all 4 direction (right, up, left, down)
    // if the cell is not visited yet and contains ' '
    for (int i = 0; i < 4; i++) {
        int xx = x + R[i];
        int yy = y + C[i];
        
        if (xx >=0 && xx < m && yy >= 0 && yy < n) {
            if (!vis[xx][yy] && grid[xx][yy] == ' ')
                dfs(xx, yy);
        }
    }
}

int main() {
    // input the grid size;
    scanf("%d %d", &m, &n);
    getchar();

    // input the grid
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%c", &grid[i][j]);
        }
        getchar();
    }

    // initialize
    int spaceEnclosedCount = 0;
    memset(vis, false, sizeof(vis));

    // iterate only for inner cells not the boundary cells
    for (int i = 1; i < m - 1; i++) {
        for (int j = 1; j < n - 1; j++) {
            if (!vis[i][j] && grid[i][j] == ' ') {
                wentToBoundary = false;
                dfs(i, j);

                if (!wentToBoundary) {
                    spaceEnclosedCount++;
                }
            }
        }
    }

    printf("number of area enclosed by spaces: %d\n", spaceEnclosedCount);

    return 0;
}

Upvotes: 3

Related Questions