aboutsummaryrefslogtreecommitdiff
path: root/find_group_farmland.c
blob: dcbbd6e038b82e2078157246d8ce9e95443e06bb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 1992. Find All Groups of Farmland
#include "leetcode.h"

/*
 * given a 0-indexed 'm * n' binary matrix 'land' where a 0 represents a hectare
 * of forested land and a 1 represents a hectare of farmland. to keep the land
 * organised, there are designated rectangular areas of hectares that consist
 * entirely of farmland. these rectangular areas are called groups. no two
 * groups are adjacent, meaning farmland in one group is not four directionally
 * adjacent to another farmland in another group. return a 2d array containing
 * the 4 length arrays described above for each group o farmland in 'land'.
 */

void dfs(int **land, int rows, int cols, int r, int c, int *top_left,
         int *bottom_right, int *count) {
  if (r < 0 || r >= rows || c < 0 || c >= cols || !land[r][c])
    return;
  (*count)++;
  if (r < top_left[0])
    top_left[0] = r;
  if (c < top_left[1])
    top_left[1] = c;
  if (r > bottom_right[0])
    bottom_right[0] = r;
  if (c > bottom_right[1])
    bottom_right[1] = c;
  land[r][c] = 0;
  dfs(land, rows, cols, r + 1, c, top_left, bottom_right, count);
  dfs(land, rows, cols, r - 1, c, top_left, bottom_right, count);
  dfs(land, rows, cols, r, c + 1, top_left, bottom_right, count);
  dfs(land, rows, cols, r, c - 1, top_left, bottom_right, count);
}

int **findFarmland(int **land, int landSize, int *landColSize, int *returnSize,
                   int **returnColumnSizes) {
  int m = landSize, n = *landColSize;
  int **ans = (int **)malloc(sizeof(int *) * m * n);
  *returnColumnSizes = (int *)malloc(sizeof(int) * (m * n));
  *returnSize = 0;
  for (int i = 0; i < m; i++)
    for (int j = 0; j < n; j++)
      if (land[i][j] == '1') {
        int top_left[2] = {i, j}, bottom_right[2] = {i, j}, cnt = 0, group[4];
        dfs(land, m, n, i, j, top_left, bottom_right, &cnt);
        group[0] = top_left[0];
        group[1] = top_left[1];
        group[2] = bottom_right[0];
        group[3] = bottom_right[1];
        ans[*returnSize] = group;
        (*returnColumnSizes)[*returnSize] = 4;
        (*returnSize)++;
      }
  return ans;
}