c - 找到“岛屿”区域的算法是什么？

Question

该程序应找到岛屿区域。矩阵中的1表示岛屿，而0表示水域。

所以我有一个程序只扫描和打印它们周围的岛屿和水域：

#include <stdio.h>

int main() {

    int rows, columns;
    scanf("%d %d", &rows, &columns);

    if(rows>10 || columns>10) {
        return 0;
    }else {
        int islands[rows][columns];

        for(int i=0; i<rows; i++){
            for(int j=0; j<columns; j++){
                scanf("%d", &islands[i][j]);
            }
        }

        for(int i=0; i<rows; i++){
            for(int j=0; j<columns; j++){
                printf("%d ", islands[i][j]);
            }
            printf("\n");
        }


    }

}

最大限度。代表我们岛屿的矩阵数量为 10x10。

例如，如果用户输入下一个数字：

3 3 //for rows and columns
1 0 1
1 0 0
0 0 0

可以看出，第一个岛在matrix[0][0]和matrix[1][0]处为 1 ，第二个岛在matrix[0][2]处。

因此，输出将是2 1因为这些是岛屿区域。

我一直在用头撞墙，但仍然找不到这样做的方法。解决问题的可能方法是什么？

标签： c

Answer 1

为此，您必须用相同的字符填充一个岛屿。您可以使用递归函数来执行此操作。它只是看（x，y）上的字符，如果字符是一个空岛，我们填充它并查看四个相邻的角。

void fill_island(char pattern, int x, int y, char **map, int size_x, int size_y) {
   if (map[x][y] == 1)
      map[x][y] = pattern; // fill the island
   else
      return; // if we are out of the island we stop this branch.
   if (x - 1 >= 0)
      fill_island(pattern, x - 1, y, map, size_x, size_y);
   if (x + 1 < size_x)
      fill_island(pattern, x + 1, y, map, size_x, size_y);
   if (y - 1 >= 0)
      fill_island(pattern, x, y - 1, map, size_x, size_y);
   if (y + 1 < size_y)
      fill_island(pattern, x, y + 1, map, size_x, size_y);
}

在您的主函数中，您必须遍历所有矩阵并调用填充函数

char pattern = 'a';
for (int x ; x < size_x ; x++)
   for (int y ; y < size_y ; y++) {
       if (map[x][y] == '1') {
          fill_island(pattern, x, y, map, size_x, size_y);
          pattern++;
       }
}

然后您只需计算每个字符即可知道岛屿的大小并对结果进行排序以获得预期的输出。