找到完整的矩形封闭0 [英] Finding complete rectangles enclosing 0

问题描述

有在给定的1000×1000阵列多样矩形。在＆LT;图1＆GT; ，串行1显示为黄色细胞是长方形的格局。矩形的最小尺寸＆LT;图1＆GT; 是3×3显示为绿色的细胞

There are diverse rectangles in given 1000 x 1000 arrays. in <Figure 1>, the serial "1" displayed as yellow cell is the pattern of rectangle. The minimum size of rectangle in <Figure 1> is 3 x 3 displayed as green cell.

应该有中的至少一个0的矩形内。

There should be at least one of ‘0’ inside the rectangle.

但是，在此阵列中，存在着未封闭的形状或直线图案也

But, in this array, there exists unclosed shape or straight line pattern also.

（数组的初始值是0，并且图案是重新presented一系列'1'，它们不重叠或包括彼此。）

(The initial value of array is ‘0’, and the patterns are represented a series of ‘1’. They are not overlapped or included each other.)

什么将会是有效的算法来找到除了未封闭的形状或直线阵列中的完整regtangles？例如，在上面完全矩形的数目的数字是3

What could be an efficient algorithm to find the complete regtangles in the array except unclosed shape or straight line? For example in the figure above the number of complete rectangles is 3

推荐答案

这是很简单的。如果你有 N 广场，你可以指望的矩形中 O（N）。

This is quite simple. If you have n squares, you can count the rectangles in O(n).

假设：

• 每个有效矩形的边界不与非有效路径共享任何细胞。
• 如果一个四边形是在另一个，你会很高兴发现它们

您将需要额外的内存一样大的投入。让我们把这个访问并初始化为0。

You would need extra memory as big as the input. Let's call this visited and initialize with 0.

让我们先构造一个辅助函数：

Let's first construct a helper function:

is_rectangle(square s)
    from s, go right while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go down while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go left while you see 1s and visited is 0
        mark them as 1 in visited
    if less than 3 steps
        return 0
    then, go up while you see 1s and visited is 0
        mark them as 1 in visited
    if then one above is not s
        return 0
    return 1

此功能基本上跟踪中的右 - 下 - 左和检查方向的1秒，如果条件满足（长度至少为3并到达起始位置）。这也标志着参观了广场。

This function basically traces the 1s in the directions of right-down-left-up and checks if the conditions are met (length at least 3 and reaching the starting position). It also marks the visited squares.

重要的是要注意有关该功能的，是它正常工作只有在初始广场是左上角。

The important thing to notice about this function, is that it works correctly only if the initial square is the top-left corner.

现在，该问题的解决方法非常简单：

Now, the solution to the problem is easy:

num_rectangles = 0
initialize visited to 0 (rows x columns)
for r in rows
    for c in columns
        if visitied[r][c] or image[r][c] == 0
            continue
        num_rectangles += is_rectangle(<r,c>)
return num_rectangles

下面是如何执行的算法：

Here is how the algorithm executes:

1.失败（并标记）坏矩形的一部分

1. Failed (and marked) part of a bad rectangle

2.发现（并标记）的矩形。

2. Found (and marked) a rectangle.

3.在单个正方形失败（垂直线）的

3. Failed on a single square (of a vertical line)

4.在一个正方形失败（垂直线）

4. Failed on a single square (of a vertical line)

5.在一个正方形失败（垂直线）

5. Failed on a single square (of a vertical line)

6.在许多类似的步骤，找到下一个矩形。

6. After many similar steps, found the next rectangle.

7。而接下来的矩形

7. And the next rectangle

8.算法结束

8. Algorithm end

这篇关于找到完整的矩形封闭0的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！