900 LeetCode Problems Solved

Achieving 900th LeetCode problems solved. LeetCoding is a hobby of mine.

For this problem, it is a simple Breadth-First-Search (BFS). Helps that no two farmlands are connected. Some calculation necessary to finding the extremities of the farmland. Code is down below, cheers, ACC.

Find All Groups of Farmland - LeetCode

1992. Find All Groups of Farmland

Medium

You are given a 0-indexed m x 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 organized, 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 a different group.

land can be represented by a coordinate system where the top left corner of land is (0, 0) and the bottom right corner of land is (m-1, n-1). Find the coordinates of the top left and bottom right corner of each group of farmland. A group of farmland with a top left corner at (r1, c1) and a bottom right corner at (r2, c2) is represented by the 4-length array [r1, c1, r2, c2].

Return a 2D array containing the 4-length arrays described above for each group of farmland in land. If there are no groups of farmland, return an empty array. You may return the answer in any order.

 

Example 1:

Input: land = [[1,0,0],[0,1,1],[0,1,1]]
Output: [[0,0,0,0],[1,1,2,2]]
Explanation:
The first group has a top left corner at land[0][0] and a bottom right corner at land[0][0].
The second group has a top left corner at land[1][1] and a bottom right corner at land[2][2].

Example 2:

Input: land = [[1,1],[1,1]]
Output: [[0,0,1,1]]
Explanation:
The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].

Example 3:

Input: land = [[0]]
Output: []
Explanation:
There are no groups of farmland.

 

Constraints:

• m == land.length
• n == land[i].length
• 1 <= m, n <= 300
• land consists of only 0's and 1's.
• Groups of farmland are rectangular in shape.

public int[][] FindFarmland(int[][] land)
{
    List list = new List();

    for (int row = 0; row < land.Length; row++)
    {
        for (int col = 0; col < land[row].Length; col++)
        {
            if (land[row][col] == 1)
            {
                int topRow = land.Length;
                int topCol = land[row].Length;
                int botRow = -1;
                int botCol = -1;

                CoverFarmland(land,
                                row,
                                col,
                                ref topRow,
                                ref topCol,
                                ref botRow,
                                ref botCol);

                list.Add(new int[] { topRow, topCol, botRow, botCol });
            }
        }
    }

    return list.ToArray();
}

private void CoverFarmland(int[][] land,
                            int row,
                            int col,
                            ref int topRow,
                            ref int topCol,
                            ref int botRow,
                            ref int botCol)
{
    Queue queue = new Queue();
    QueueItem qi = new QueueItem(row, col);
    land[row][col] = 0;
    queue.Enqueue(qi);

    int[] rowOffset = { 1, -1, 0, 0 };
    int[] colOffset = { 0, 0, 1, -1 };

    while (queue.Count > 0)
    {
        QueueItem currentQi = queue.Dequeue();

        topRow = Math.Min(topRow, currentQi.row);
        topCol = Math.Min(topCol, currentQi.col);
        botRow = Math.Max(botRow, currentQi.row);
        botCol = Math.Max(botCol, currentQi.col);

        for (int i = 0; i < rowOffset.Length; i++)
        {
            int newRow = currentQi.row + rowOffset[i];
            int newCol = currentQi.col + colOffset[i];

            if (newRow >= 0 &&
                newRow < land.Length &&
                newCol >= 0 &&
                newCol < land[newRow].Length &&
                land[newRow][newCol] == 1)
            {
                QueueItem newQi = new QueueItem(newRow, newCol);
                land[newRow][newCol] = 0;
                queue.Enqueue(newQi);
            }
        }
    }
}

public class QueueItem
{
    public int row;
    public int col;

    public QueueItem(int row, int col)
    {
        this.row = row;
        this.col = col;
    }
}