Wsrtjtyk

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?

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 increament 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 curren 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 contans ' '

    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: %dn", spaceEnclosedCount);



    return 0;

}