C语言 递归泛色填充以查找2D数组中形状的最大面积[已关闭]

iqxoj9l9  于 2023-03-07  发布在  其他
关注(0)|答案(1)|浏览(106)

昨天关门了。
Improve this question
需要求出图形的最大面积,图形是一组有公共边的单元格(1表示单元格已填充,0表示单元格为空)。
输入:

6 10 // array size
1 1 0 0 0 0 0 1 1 0
0 1 1 1 0 1 0 1 1 0
0 1 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0 0

输出:

12 (The maximum area of a figure consisting of ones)
nkhmeac6

nkhmeac61#

用递归FloodFill算法解决我的问题的C代码

#include <stdio.h>
#include <stdlib.h>

#define MAX(a, b) ((a) > (b) ? (a) : (b))

int countArea(int x, int y, int **matrix, int n, int m)
{
    if (x >= n || x < 0 || y >= m || y < 0)
        return 0;
    if (matrix[x][y] != 1)
        return 0;
    matrix[x][y] = 2;
    return (1 + countArea(x + 1, y, matrix, n, m) + countArea(x - 1, y, matrix, n, m)
             + countArea(x, y + 1, matrix, n, m) + countArea(x, y - 1, matrix, n, m));
}

int main() {
  int n, m;
  scanf("%d %d", &n, &m);
  int **matrix = malloc(sizeof(int*) * n);
  for (int i = 0; i < n; i++) {
      matrix[i] = malloc(sizeof(int) * m);
      for(int j = 0; j < m; j++) {
          scanf("%d", &matrix[i][j]);
      }
  }
  int max_area = 0;
  for (int i = 0; i < n; i++) {
      for (int j = 0; j < m; j++) {
          if (matrix[i][j] == 1) {
              int area = countArea(i, j, matrix, n, m);
              max_area = MAX(max_area, area);
          }
      }
  }
  printf("%d", max_area);
  return 0;
}

相关问题