时间戳

首页 > 解决方案 > 在 2D M x N 网格中查找封闭空间的存在

algorithm - 在 2D M x N 网格中查找封闭空间的存在

问题描述

我的任务是使用算法在问题提供的网格中找到封闭空间的存在。空格（''）表示有洞，而井号（'#'）表示有墙。现在假设我有一个二维 M x N 网格，我如何找到是否存在封闭空间？带有封闭空间的网格示例：

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

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

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

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

起初，我试图将这个网格存储到一个字符串向量中。然后，我继续检查每个空格是散列还是空格。如果它是一个空间（它的位置现在称为initial），我会检查该空间的周围区域，直到找到一个可以从所述边缘到达的孔（空间）initial。如果是散列，我会继续网格中的下一个“正方形”。

然而，我试图暴力破解每一种可能性的算法似乎非常乏味和低效。在继续这项任务之前我是否应该了解一些其他概念（阅读有关地图、路径、树木等的更多信息）。如果有，你能告诉我先读什么吗？如果没有，请您指导我吗？

我解决此任务的方法是否正确？

标签： algorithm

解决方案

这个想法是：

  • 我们从每个未访问的空单元格开始
  • 尝试访问所有连接的空单元格
  • 如果我们可以去边界，那么这不是一个封闭的区域
  • 如果连接区域的任何单元都不是边界单元，则该区域被墙包围，我们增加计数。

c++这是计算封闭区域数量的示例实现：

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

推荐阅读