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