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}

#include <unordered_map>
using namespace std;

class Solution {
public:
    vector<int> parent, rank;

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }

    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
        int m = land.size();
        int n = land[0].size();
        parent.resize(m * n);
        rank.resize(m * n, 0);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (land[i][j] == 1) {
                    int index = i * n + j;
                    parent[index] = index;
                    if (i > 0 && land[i-1][j] == 1) {
                        unionSets(index, (i-1) * n + j);
                    }
                    if (j > 0 && land[i][j-1] == 1) {
                        unionSets(index, i * n + (j-1));
                    }
                }
            }
        }

        unordered_map<int, vector<int>> bounds;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (land[i][j] == 1) {
                    int root = find(i * n + j);
                    if (!bounds.count(root)) {
                        bounds[root] = {i, j, i, j};
                    } else {
                        bounds[root][0] = min(bounds[root][0], i);
                        bounds[root][1] = min(bounds[root][1], j);
                        bounds[root][2] = max(bounds[root][2], i);
                        bounds[root][3] = max(bounds[root][3], j);
                    }
                }
            }
        }

        vector<vector<int>> results;
        for (auto& bound : bounds) {
            results.push_back(bound.second);
        }

        return results;
    }
};