
Problem Statement
In this task, you are given a binary matrix land
where the matrix dimensions are m x n
. Within this matrix:
- A value of
0
indicates forested land. - A value of
1
indicates farmland.
The matrix is organized into distinct rectangular regions, or groups, that contain only farmland (1
s). Each group of farmland is entirely surrounded by forested land (0
s), or by the boundaries of the matrix - no group is directly adjacent to another.
The key objective is to identify these groups and determine two sets of coordinates for each:
- The top-left corner of the group.
- The bottom-right corner of the group.
These coordinates for each group are then to be returned as pairs within an array, where each group is represented by a 4-length array of the form [r1, c1, r2, c2]
. An empty array should be returned if no such groups exist.
Examples
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 only0
's and1
's.- Groups of farmland are rectangular in shape.
Approach and Intuition
Given the binary nature of the matrix and the problem's constraints, we'll approach it as a variant of the common "connected components in a graph" problem. The "farmland" (1
s) areas can be viewed as nodes in a grid graph, where contiguous patches need to be identified as separate components.
Traversing the Matrix:
- We iterate through each cell of the matrix. If we encounter a
1
, we check if it has not already been considered part of another group.
- We iterate through each cell of the matrix. If we encounter a
Group Detection using DFS/BFS:
- Starting from the initial
1
encountered, we can use a Depth-First Search (DFS) or Breadth-First Search (BFS) to explore all directly connected1
s (i.e., those that are horizontally or vertically adjacent, but not diagonally). - Keep track of the smallest and largest row and column indices reached during this exploration, as these will correspond to the top-left and bottom-right corners of the current farmland group.
- Starting from the initial
Storage and Output:
- After identifying a complete group, store its bounding coordinates
[r1, c1, r2, c2]
in the output array. - Reset and continue the matrix traversal, skipping over any cells that have already been included in a group.
- After identifying a complete group, store its bounding coordinates
The DFS/BFS ensures that each cell is visited no more than once, leading to a linear time complexity relative to the number of cells, i.e., (O(m \times n)), where (m) and (n) are the matrix dimensions. This approach efficiently handles the upper constraint limits given.
Solutions
- C++
- Java
- Python
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
), initializeendRow
andendCol
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 resetendCol
to start from the initialj
column. Repeat until reaching a row where cells directly below the currentendRow
are no longer farmland.
- Continue expanding
- After determining the extent of the rectangle, store its coordinates [top-left
(i, j)
and bottom-right(endRow - 1, endCol - 1)
] in thefarmlands
list.
- If the cell at position
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
andcols
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
andendCol
at the current indices (i
andj
). - 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]
wherei
andj
are the starting row and column, andendRow - 1
andendCol - 1
represent the ending row and column of the block. - Append these coordinates to
results
.
- Initialize
- 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:
Initialize
rows
andcols
to store the dimensions of the input grid.Create an empty list
farm_areas
to store the coordinates of each farmland area found.Iterate through each cell in the grid using a nested loop.
For each cell that contains '1', mark it as the starting point of a new farmland area.
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.
Once the full extent of the farmland is determined, append the top-left and bottom-right coordinates of the farmland area to
farm_areas
.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.
No comments yet.