1#include <stdio.h>
2#include <stdlib.h>
3#include <stdbool.h>
4#include <string.h>
5
6void bfs(int** land, bool** visited, int m, int n, int start_row, int start_col, int* end_row, int* end_col) {
7    int directions[2][2] = {{0, 1}, {1, 0}};
8    int queue[m * n][2];
9    int front = 0, back = 0;
10    queue[back][0] = start_row;
11    queue[back][1] = start_col;
12    back++;
13    visited[start_row][start_col] = true;
14    *end_row = start_row;
15    *end_col = start_col;
16
17    while (front < back) {
18        int row = queue[front][0];
19        int col = queue[front][1];
20        front++;
21        *end_row = row;
22        *end_col = col;
23
24        for (int i = 0; i < 2; i++) {
25            int new_row = row + directions[i][0];
26            int new_col = col + directions[i][1];
27            if (new_row < m && new_col < n && !visited[new_row][new_col] && land[new_row][new_col] == 1) {
28                visited[new_row][new_col] = true;
29                queue[back][0] = new_row;
30                queue[back][1] = new_col;
31                back++;
32            }
33        }
34    }
35}
36
37int** findFarmland(int** land, int m, int n, int* returnSize, int** returnColumnSizes) {
38    bool** visited = (bool**)malloc(m * sizeof(bool*));
39    for (int i = 0; i < m; i++) {
40        visited[i] = (bool*)calloc(n, sizeof(bool));
41    }
42    
43    int** results = (int**)malloc(m * n * sizeof(int*));
44    *returnColumnSizes = (int*)malloc(m * n * sizeof(int));
45    int count = 0;
46
47    for (int i = 0; i < m; i++) {
48        for (int j = 0; j < n; j++) {
49            if (land[i][j] == 1 && !visited[i][j]) {
50                int end_row, end_col;
51                bfs(land, visited, m, n, i, j, &end_row, &end_col);
52
53                results[count] = (int*)malloc(4 * sizeof(int));
54                results[count][0] = i;
55                results[count][1] = j;
56                results[count][2] = end_row;
57                results[count][3] = end_col;
58                (*returnColumnSizes)[count] = 4;
59                count++;
60            }
61        }
62    }
63
64    *returnSize = count;
65    for (int i = 0; i < m; i++) {
66        free(visited[i]);
67    }
68    free(visited);
69    return results;
70}