找到所有的农场组
难度:
标签:
题目描述
给你一个下标从 0 开始，大小为 m x n 的二进制矩阵 land ，其中 0 表示一单位的森林土地，1 表示一单位的农场土地。
为了让农场保持有序，农场土地之间以矩形的 农场组 的形式存在。每一个农场组都 仅 包含农场土地。且题目保证不会有两个农场组相邻，也就是说一个农场组中的任何一块土地都 不会 与另一个农场组的任何一块土地在四个方向上相邻。
land 可以用坐标系统表示，其中 land 左上角坐标为 (0, 0) ，右下角坐标为 (m-1, n-1) 。请你找到所有 农场组 最左上角和最右下角的坐标。一个左上角坐标为 (r1, c1) 且右下角坐标为 (r2, c2) 的 农场组 用长度为 4 的数组 [r1, c1, r2, c2] 表示。
请你返回一个二维数组，它包含若干个长度为 4 的子数组，每个子数组表示 land 中的一个 农场组 。如果没有任何农场组，请你返回一个空数组。可以以 任意顺序 返回所有农场组。
示例 1：
输入：land = [[1,0,0],[0,1,1],[0,1,1]] 输出：[[0,0,0,0],[1,1,2,2]] 解释： 第一个农场组的左上角为 land[0][0] ，右下角为 land[0][0] 。 第二个农场组的左上角为 land[1][1] ，右下角为 land[2][2] 。
示例 2：
输入：land = [[1,1],[1,1]] 输出：[[0,0,1,1]] 解释： 第一个农场组左上角为 land[0][0] ，右下角为 land[1][1] 。
示例 3：
输入：land = [[0]] 输出：[] 解释： 没有任何农场组。
提示：
m == land.lengthn == land[i].length1 <= m, n <= 300land只包含0和1。- 农场组都是 矩形 的形状。
代码结果
运行时间: 90 ms, 内存: 29.1 MB
/*
* 思路：
* 1. 使用流式处理来查找和记录农场组的边界。
* 2. 遍历矩阵，通过条件过滤找到每个农场组的左上角坐标。
* 3. 使用递归函数找到农场组的右下角坐标。
* 4. 返回所有农场组的坐标。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public List<int[]> findFarmland(int[][] land) {
int m = land.length;
int n = land[0].length;
boolean[][] visited = new boolean[m][n];
return IntStream.range(0, m).boxed()
.flatMap(i -> IntStream.range(0, n).mapToObj(j -> new int[]{i, j}))
.filter(coord -> land[coord[0]][coord[1]] == 1 && !visited[coord[0]][coord[1]])
.map(coord -> {
int[] farm = new int[4];
farm[0] = coord[0];
farm[1] = coord[1];
findFarm(land, visited, coord[0], coord[1], farm);
return farm;
})
.collect(Collectors.toList());
}
private void findFarm(int[][] land, boolean[][] visited, int i, int j, int[] farm) {
int m = land.length;
int n = land[0].length;
if (i < 0 || i >= m || j < 0 || j >= n || land[i][j] == 0 || visited[i][j]) {
return;
}
visited[i][j] = true;
farm[2] = i;
farm[3] = j;
findFarm(land, visited, i + 1, j, farm);
findFarm(land, visited, i, j + 1, farm);
}
}
解释
方法:
The solution involves scanning each cell of the matrix. If a cell is the top-left corner of a new farmland group (i.e., it is '1' and neither the left neighbor nor the top neighbor is '1'), the algorithm then explores downwards and rightwards to determine the extent of this farmland group. The exploration continues until it finds a row or a column that does not consist entirely of '1's, marking the boundaries of the rectangle. These boundaries (top-left and bottom-right corners) are stored in the result list. If a cell is not the beginning of a new farmland group or is a forest land ('0'), the algorithm simply continues to the next cell.
时间复杂度:
O(m*n)
空间复杂度:
O(1) additional space
代码细节讲解
🦆
在判断一个单元格是否是新农场组的左上角时，为什么只检查左边和上边的相邻单元格而不是四个方向的相邻单元格？
▷🦆
算法在确定农场组的右边界和下边界时，为什么只沿着列向下扫描和沿着行向右扫描，而不检查每个单元格的四周是否有相邻的其他农场组？
▷🦆
如果输入矩阵的大小为 0，即 m 或 n 为 0，该算法是否能正确处理并返回空数组？
▷🦆
算法在发现新的农场组时是如何保证不会重复计算已经标记过的农场组的？
▷