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}

using System.Collections.Generic;

public class Solution {
    public int[][] FindFarmland(int[][] land) {
        int m = land.Length, n = land[0].Length;
        int[] parent = new int[m * n];
        int[] rank = new int[m * n];

        for (int i = 0; i < m * n; i++) {
            parent[i] = i;
        }

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

        void Union(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]++;
                }
            }
        }

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

        var bounds = new Dictionary<int, int[]>();
        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.ContainsKey(root)) {
                        bounds[root] = new int[] { i, j, i, j };
                    } else {
                        bounds[root][0] = Math.Min(bounds[root][0], i);
                        bounds[root][1] = Math.Min(bounds[root][1], j);
                        bounds[root][2] = Math.Max(bounds[root][2], i);
                        bounds[root][3] = Math.Max(bounds[root][3], j);
                    }
                }
            }
        }

        var result = new List<int[]>(bounds.Values); 
        return result.ToArray();
    }
}