java - 如何在java中的简单矩阵中找到非相交的边界矩形？

Question

我有一个二维矩阵，看起来像

matr=([[0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 1., 0., 0., 0.],
       [0., 0., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0., 0., 0., 0.]])

我需要编写 Java 代码来找到值 1 的非相交边界矩形

这里也有类似的问题: Fill Bounding Boxes in 2D array

但是解决方案是在 Python 上使用一些特殊的库，我需要在 Java 中实现它，而且在这种情况下我需要找到不相交的框

假设我们可以将点和矩形存储为

class Point{
    int x, y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

class Rectangle{
    Point topLeft, bottomRight;

    public Rectangle(Point topLeft, Point bottomRight) {
        this.topLeft = topLeft;
        this.bottomRight = bottomRight;
    }
}

在上面提供的示例中，答案应该是 Rectangle(Point(2,2), Point(5,4))，其他矩形相交，这就是为什么不需要计算它们

Answer 1

您可以使用 BFS (Breadth-first search)执行此操作的算法。

步骤如下:

1. 遍历所有点(Matrix 中的所有值)并检查一个点是否具有值 1
2. 从一个包含1
的未访问点开始
3. 运行 BFS 以找到从该点开始的所有连接点。
4. 标记/标记所有访问过的点。
5. 计算连接点中的左上点和右下点。
6. 从 2 开始。