You are given a 2D grid representing a piece of farmland, where the value 1 represents cultivated land and 0 represents uncultivated land. A group of farmland is a connected region of cultivated land, where a cell is considered connected to its adjacent cells horizontally and vertically. You need to find all groups of farmland and return their coordinates as a list of 4-element arrays.
Each 4-element array contains [r1, c1, r2, c2], where (r1, c1) and (r2, c2) represent the top-left and bottom-right coordinates of the rectangular region of cultivated land for each group.
Table of Contents
Sample Input:
Farmland:
[
[1, 0, 0, 1],
[1, 1, 0, 1],
[0, 1, 1, 1]
]
Expected Output:
Groups of Farmland:
[[0, 0, 0, 0], [0, 3, 1, 3], [1, 0, 2, 1], [2, 2, 2, 3]]
In this example, there are four groups of farmland in the grid, and their coordinates are returned as a list of 4-element arrays.
Time and Space Complexity:
The time complexity of the algorithm is O(m * n), where ‘m’ is the number of rows and ‘n’ is the number of columns in the grid. In the worst case, we may have to visit each cell once to find all groups of farmland.
The space complexity is O(m * n) as well, due to the recursion stack and the output list, which can grow to the size of the grid in the worst case.
C++ solution:
#include <iostream>
#include <vector>
void findFarmlandRecursive(std::vector<std::vector<int>>& grid, int row, int col, int& farmlandCount, int& farmlandRow2, int& farmlandCol2) {
int rows = grid.size();
int cols = grid[0].size();
// Base case: If the current cell is out of bounds or it is not cultivated land (1), return.
if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] != 1) {
return;
}
// Mark the current cell as visited by changing it to 0 (uncultivated land).
grid[row][col] = 0;
// Update the bottom-right coordinates of the current group of farmland.
farmlandRow2 = row;
farmlandCol2 = col;
// Recursively explore all adjacent cells (top, bottom, left, right).
findFarmlandRecursive(grid, row - 1, col, farmlandCount, farmlandRow2, farmlandCol2); // Top neighbor
findFarmlandRecursive(grid, row + 1, col, farmlandCount, farmlandRow2, farmlandCol2); // Bottom neighbor
findFarmlandRecursive(grid, row, col - 1, farmlandCount, farmlandRow2, farmlandCol2); // Left neighbor
findFarmlandRecursive(grid, row, col + 1, farmlandCount, farmlandRow2, farmlandCol2); // Right neighbor
}
std::vector<std::vector<int>> findFarmland(std::vector<std::vector<int>>& grid) {
int rows = grid.size();
int cols = grid[0].size();
std::vector<std::vector<int>> result;
// Iterate through the grid to find each group of farmland.
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
// If the cell is cultivated land (1), start the recursion to find the group.
if (grid[i][j] == 1) {
int farmlandCount = 0;
int farmlandRow2 = i;
int farmlandCol2 = j;
// Recursively find the bottom-right coordinates of the group of farmland.
findFarmlandRecursive(grid, i, j, farmlandCount, farmlandRow2, farmlandCol2);
// Add the coordinates of the group of farmland to the result.
result.push_back({i, j, farmlandRow2, farmlandCol2});
}
}
}
return result;
}
int main() {
// Construct the farmland grid for the sample input
std::vector<std::vector<int>> farmlandGrid = {
{1, 0, 0, 1},
{1, 1, 0, 1},
{0, 1, 1, 1}
};
// Find all groups of farmland in the grid
std::vector<std::vector<int>> groupsOfFarmland = findFarmland(farmlandGrid);
// Print the result
std::cout << "Groups of Farmland:" << std::endl;
for (const auto& group : groupsOfFarmland) {
std::cout << "[";
for (int i = 0; i < group.size(); ++i) {
std::cout << group[i];
if (i < group.size() - 1) {
std::cout << ", ";
}
}
std::cout << "]" << std::endl;
}
return 0;
}
The findFarmlandRecursive function is a helper function that performs a depth-first search (DFS) to find a group of farmland. It starts from a given cell of cultivated land (1) and marks it as visited by changing it to uncultivated land (0). Then, it recursively explores all its adjacent cells (top, bottom, left, right) that are also cultivated land (1) and updates the bottom-right coordinates of the current group.
The findFarmland function is the entry point of the algorithm. It iterates through the grid to find each group of farmland. Whenever it finds a cell of cultivated land (1), it starts the recursion to find the entire group and adds the top-left and bottom-right coordinates of the group to the result.
In the given example, the function will correctly find all groups of farmland in the grid, and the output will be as follows:
Groups of Farmland:
[0, 0, 0, 0], [0, 3, 1, 3], [1, 0, 2, 1], [2, 2, 2, 3]