1992. Find All Groups of Farmland
Medium
You are given a 0indexed 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 fourdirectionally 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 (m1, n1)
. 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 (r_{1}, c_{1})
and a bottom right corner at (r_{2}, c_{2})
is represented by the 4length array [r_{1}, c_{1}, r_{2}, c_{2}]
.
Return a 2D array containing the 4length 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 atland[0][0]
.
The second group has a top left corner atland[1][1]
and a bottom right corner atland[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 atland[1][1]
.
Example 3:
 Input: land = [[0]]
 Output: []

Explanation:
There are no groups of farmland.
Constraints:
m == land.length/code>
n == land[i].length
1 <= m, n <= 300

land
consists of only0
's and1
's.  Groups of farmland are rectangular
in shape
.
class Solution {
/**
* @param Integer[][] $land
* @return Integer[][]
*/
function findFarmland($land) {
$row = count($land);
$col = count($land[0]);
$ans = [];
for ($y = 0; $y < $row; ++$y) {
for ($x = 0; $x < $col; ++$x) {
if (!$land[$y][$x])
continue;
$pos = array_fill(0, 4, 0);
$pos[0] = $y;
$pos[1] = $x;
$q = new SplQueue();
$q>enqueue([$y, $x]);
while (!$q>isEmpty()) {
list($y1, $x1) = $q>dequeue();
if ($y1 == 1 or $y1 == $row or $x1 == 1 or $x1 == $col or !$land[$y1][$x1])
continue;
$land[$y1][$x1] = 0;
$pos[2] = $y1;
$pos[3] = $x1;
$q>enqueue([$y1, $x1+1]);
$q>enqueue([$y1+1, $x1]);
}
$ans[] = $pos;
}
}
return $ans;
}
}
Contact Links
Top comments (0)