找到包含0的完整矩形

Question

在给定的1000 x 1000阵列中存在不同的矩形.在<Figure 1>,显示为黄色单元格的序列"1"是矩形的图案.矩形的最小尺寸<Figure 1>为3 x 3,显示为绿色单元格.

矩形内应该至少有一个'0'.

但是,在该阵列中,也存在未闭合的形状或直线图案.

(数组的初始值为'0',模式表示一系列'1'.它们不重叠或相互包含.)

什么是一个有效的算法来找到阵列中的完整的整数,除了未闭合的形状或直线？例如,在上图中,完整矩形的数量是3

Answer 1

这很简单.如果你有n正方形,你可以计算矩形O(n).

假设:

• 每个有效矩形的边框不共享任何具有无效路径的单元格.
• 如果一个矩形在另一个矩形内,你会很高兴找到它们

你需要额外的内存和输入一样大.我们调用它visited并用0初始化.

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

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并到达起始位置).它也标志着访问过的广场.

关于这个函数需要注意的重要一点是,只有当初始方格是左上角时它才能正常工作.

现在,解决问题的方法很简单:

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

以下是算法的执行方式:

1.失败(并标记)坏矩形的一部分

2.找到(并标记)一个矩形.

3.单个方格(垂直线)失败

4.单个方格(垂直线)失败

5.单个方格(垂直线)失败

6.经过许多类似的步骤,找到下一个矩形.

7.下一个矩形

8.算法结束

Answer 2

这就是我的想法，资源效率可能相当低。对此一无所知。

1. 沿着一行遍历，除非找到至少 31秒。
2. 向下遍历并对下面的行进行& 操作 -->如果它是有效的矩形，boolean它们应该得到以下格式。100..001（假设你可以完成所有boolean操作）
3. 当您在步骤 2 中找到至少一行，最后找到所有1s 时，您就找到了一个矩形。
4. 重复该行的下一个元素！