Find All Groups of Farmland

class Solution {
public:
    vector<vector<int>> detectFarmland(vector<vector<int>>& landMatrix) {
        int rows = landMatrix.size(), cols = landMatrix[0].size();
        vector<vector<int>> farmlands;
        
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (landMatrix[i][j] == 1) {
                    int endRow = i, endCol = j;
                    
                    while (endRow < rows && landMatrix[endRow][j] == 1) {
                        while (endCol < cols && landMatrix[endRow][endCol] == 1) {
                            landMatrix[endRow][endCol] = 0;
                            endCol++;
                        }
                        endRow++;
                        endCol = j;
                    }

                    farmlands.push_back({i, j, endRow - 1, endCol - 1});
                }
            }
        }
        
        return farmlands;
    }
};

The provided C++ solution describes an approach to find all contiguous rectangular groups of farmland within a given 2D grid, where each cell contains either a 1 (representing farmland) or a 0 (representing non-farmland). The solution utilizes a vector<vector<int>> to represent the output list of farmland rectangles, which are characterized by their top-left and bottom-right corner coordinates.

Upon initiating the detectFarmland function, the following steps are taken:

• Initialize the rows and columns based on the input grid's dimensions.

• Define a vector<vector<int>> farmlands to gather the coordinates of each detected rectangular farmland area.

• Iterate through each cell in the grid using nested loops:

  • If the cell at position (i, j) is a farm cell (landMatrix[i][j] == 1), initialize endRow and endCol to the starting coordinates (i, j).
  • Expand in both the horizontal (columns) and vertical (rows) directions to determine the full extent of the rectangle:
    • Continue expanding endCol while cells in the same row and increasing columns contain a 1, setting cells to 0 as they are absorbed into a rectangle to avoid recounting.
    • After expanding horizontally for a given row, increment endRow and reset endCol to start from the initial j column. Repeat until reaching a row where cells directly below the current endRow are no longer farmland.
  • After determining the extent of the rectangle, store its coordinates [top-left (i, j) and bottom-right (endRow - 1, endCol - 1)] in the farmlands list.

• Return the completed list of farmland rectangles farmlands.

This approach ensures that each part of the farmland is only visited and counted once, heavily relying on updating the matrix in-place to mark cells that are already included in a farmland group. The end result is an efficient categorization of all farmland areas, allowing for easy identification of their boundaries within the 2D grid.

class FarmFinder {
    public int[][] identifyFarms(int[][] field) {
        int rows = field.length, cols = field[0].length;
        List<int[]> results = new ArrayList<>();

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (field[i][j] == 1) {
                    int endRow = i, endCol = j;

                    for (endRow = i; endRow < rows && field[endRow][j] == 1; endRow++) {
                        for (endCol = j; endCol < cols && field[endRow][endCol] == 1; endCol++) {
                            field[endRow][endCol] = 0;
                        }
                    }

                    int[] coordinate = new int[] {i, j, endRow - 1, endCol - 1};
                    results.add(coordinate);
                }
            }
        }
        return results.toArray(new int[results.size()][]);
    }
}

The provided Java program defines a class FarmFinder with a method identifyFarms, which aims to locate continuous groups of farmland on a grid. The grid is represented by a 2D integer array where '1' indicates farmland and '0' denotes an empty plot. The goal is to find all rectangles of continuous farmland and return their coordinates, where each rectangle is defined by top-left and bottom-right corners.

Here's how the method identifyFarms performs this task:

• Initialize rows and cols to store the dimensions of the input grid (field).
• Create a list results to keep track of identified farmland coordinates.
• Loop through each cell of the grid using nested loops.
• When a cell with value '1' is found:
  • Initialize endRow and endCol at the current indices (i and j).
  • Use nested loops to expand downwards and rightwards to find the boundaries of the farmland block. During this expansion, mark each traversed '1' as '0' to avoid recounting the same cells.
  • After finding the extent of the block, save the coordinates [i, j, endRow - 1, endCol - 1] where i and j are the starting row and column, and endRow - 1 and endCol - 1 represent the ending row and column of the block.
  • Append these coordinates to results.
• Convert the results list to an array of arrays and return it, providing the list of all found farmland groups as output.

In summary, this method effectively finds and marks each group of connected '1's in the given grid and records their boundaries, making it efficient to determine all distinct groups of farmland.

class Solution:
    def locateFarmingArea(self, grid: List[List[int]]) -> List[List[int]]:
        rows, cols = len(grid), len(grid[0])
        farm_areas = []
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j]:
                    endRow, endCol = i, j
                    
                    while endRow < rows and grid[endRow][j]:
                        endCol = j
                        while endCol < cols and grid[endRow][endCol]:
                            grid[endRow][endCol] = 0
                            endCol += 1
                        endRow += 1
                    
                    farm_areas.append([i, j, endRow - 1, endCol - 1])
        
        return farm_areas

The provided Python solution finds all the contiguous groups of land marked as '1' in a given 2D grid, which represents farmland areas. Below is the step-by-step explanation of the approach used:

1. Initialize rows and cols to store the dimensions of the input grid.

2. Create an empty list farm_areas to store the coordinates of each farmland area found.

3. Iterate through each cell in the grid using a nested loop.

4. For each cell that contains '1', mark it as the starting point of a new farmland area.

5. Use two nested while loops to explore the extent of the farmland area horizontally and vertically:

   • Mark visited parts of the farm as '0' to avoid revisiting them.
   • Expand horizontally until a '0' is encountered or the end of the column is reached.
   • Expand vertically until a '0' is encountered or the end of the row is reached.

6. Once the full extent of the farmland is determined, append the top-left and bottom-right coordinates of the farmland area to farm_areas.

7. Return the list farm_areas which contains the boundaries for all farmland groups found in the grid.

This method effectively identifies and records each contiguous block of farmland using a modified depth-first search that marks parts of the farm as processed by setting them to '0', preventing redundant processing and capturing the correct dimensions of each farmland area.