在二维MxN网格中寻找封闭空间的存在性

Question

我的任务是使用算法在问题提供的网格中找到封闭空间的存在。空格("(表示有一个洞，而哈希("#"(则表示有一面墙。现在假设我有一个二维的MxN网格，我如何发现是否存在封闭空间？具有封闭空间的网格示例：

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

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

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

我解决这项任务的方法正确吗？

Answer 1

想法是：

• 我们从每个未访问的空单元格开始
• 尝试访问所有连接的空单元格
• 如果我们能到达边界，那么这就不是一个封闭的区域
• 如果连接区域中没有一个单元是边界单元，那么该区域被墙包围，我们增加计数

以下是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: %dn", spaceEnclosedCount);
return 0;
}