在网格 Python 中查找模式

我已经实现了三种算法。第一个算法是Simple，使用最简单的嵌套循环方法，它具有O(N^5) 时间复杂度（对于我们的情况N，其中是输入网格的一侧10），对于我们的输入大小10x10时间来说O(10^5)是相当好的。代码中的算法 ID 是algo = 0。如果您只想查看该算法，请跳转到------ Simple Algorithm代码内的行。第二种算法是Advanced，采用动态规划方法，其复杂度O(N^3)比第一种算法快得多。代码中的算法 ID 是algo = 1。跳转到------- Advanced Algorithm代码内的行。我实现的第三个算法Simple-ListComp只是为了好玩，它几乎与相同Simple，相同的O(N^5)复杂性，但使用 Python 的列表理解而不是常规循环，这就是为什么它更短，也慢一点，因为没有使用一些优化。代码中的算法 ID 是algo = 2。跳转到------- Simple-ListComp Algorithm代码内的行以查看算法。除了算法之外，其余代码还实现检查结果的正确性（算法之间的双重检查）、打印结果、生成文本输入。代码分为解决任务函数solve()和测试函数test()。solve()函数有许多参数来允许配置函数的行为。所有主要代码行均由注释记录，阅读它们以了解如何使用代码。基本上，如果s变量包含带有网格元素的多行文本，就像您的问题一样，您只需运行solve(s, text = True)它就会解决任务并打印结果。algo = 0, check = False此外，您还可以通过给出求解函数的下一个参数（此处 0 表示算法 0 ）从两个版本（0（简单）和 1（高级）和 2（简单列表计算））中选择算法。查看test()函数体以查看最简单的用法示例。算法默认输出到控制台的所有簇，从最大到最小，最大的用.符号表示，其余的用B, C, D, ...,Z符号表示。show_non_max = False如果您只想显示第一个（最大）簇，您可以在求解函数中设置参数。我将解释简单算法：基本上算法的作用是 - 它搜索所有可能的有角度的1s矩形并将其中最大的矩形的信息存储到ma二维数组中。Top-left这个矩形的点是(i, j), top-right- (i, k), bottom-left- (l, j + angle_offset), bottom-right- (l, k + angle_offset)，所有 4 个角，这就是我们有这么多循环的原因。在外部两个i（行）、j（列）循环中，我们迭代整个网格，该(i, j)位置将是矩形top-left的点1s，我们需要迭代整个网格，因为所有可能的1s矩形可能位于整个网格的top-left任何点。(row, col)在循环开始时，j我们检查位置处的网格应(i, j)始终包含1，因为在循环内部我们仅搜索所有矩形1s。k循环遍历矩形的所有可能top-right位置。如果等于，我们应该跳出循环，因为没有必要进一步向右扩展，因为这样的矩形将始终包含。(i, k)1s(i, k)0k0在之前的循环中，我们固定了top-left矩形top-right的角点。现在我们需要搜索两个底角。为此，我们需要以不同角度向下延伸矩形，直到到达第一个0。off循环尝试以所有可能的角度向下延伸矩形（0（垂直垂直），+1（45从上到下向右移动的度数），-1（-45度）），off基本上是grid[y][x]“上方”的数字（对应于 by Y）grid[y + 1][x + off]。lY尝试以不同角度向下（方向）延伸矩形off。它被扩展到第一个，0因为它不能进一步扩展（因为每个这样的矩形已经包含0）。循环内部l有一个if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:条件，基本上这if是为了检查矩形的最后一行是否包含所有内容，1如果不是，if则会跳出循环。此条件比较两个list切片是否相等。矩形的最后一行从点(l, j + angle_offset)（表达式max(0, j + off * (l - i))，最大限制为0 <= X）到点(l, k + angle_offset)（表达式min(k + 1 + off * (l - i), c)，最小限制为X < c）。在循环内部l还有其他行，ry, rx = l, k + off * (l - i)计算bottom-right矩形的点，(ry, rx)即(l, k + angle_offset)，该(ry, rx)位置用于存储在ma数组中找到的最大值，该数组存储所有找到的最大矩形，包含有关在点ma[ry][rx]处的矩形的信息。bottom-right(ry, rx)rv = (l + 1 - i, k + 1 - j, off)line 计算ma[ry][rx]数组条目的新的可能候选者，之所以可能，ma[ry][rx]是因为仅当新候选者具有更大的面积时才更新1s。这里元组rv[0]内的值rv包含height这样的矩形，rv[1]包含width这样的矩形（width等于矩形底行的长度），rv[2]包含这样的矩形的角度。条件if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:及其主体仅检查rv面积是否大于数组内的当前最大值ma[ry][rx]，如果大于则更新此数组条目（ma[ry][rx] = rv）。我会提醒您，其中包含有关当前找到的最大面积矩形的ma[ry][rx]信息，该矩形具有、和。(width, height, angle)bottom-right(ry, rx)widthheightangle完毕！算法运行后，数组ma包含有关所有最大面积有角度的矩形（簇）的信息1s，以便所有簇都可以恢复并稍后打印到控制台。Largest of all such 1s-clusters 等于 some rv0 = ma[ry0][rx0]，只需迭代一次的所有元素ma并找到这样的点(ry0, rx0)，以使ma[ry0][rx0][0] * ma[ry0][rx0][1]（面积）最大。然后最大的簇将有bottom-rightpoint (ry0, rx0)、bottom-leftpoint (ry0, rx0 - rv0[1] + 1)、top-rightpoint (ry0 - rv0[0] + 1, rx0 - rv0[2] * (rv0[0] - 1))、top-leftpoint (ry0 - rv0[0] + 1, rx0 - rv0[1] + 1 - rv0[2] * (rv0[0] - 1))（这里只是角度偏移，即第一行与矩形的最后一行相比rv0[2] * (rv0[0] - 1)移动了多少）。X在线尝试一下！# ----------------- Main function solving task -----------------def solve(    grid, *,    algo = 1, # Choose algorithm, 0 - Simple, 1 - Advanced, 2 - Simple-ListComp    check = True, # If True run all algorithms and check that they produce same results, otherwise run just chosen algorithm without checking    text = False, # If true then grid is a multi-line text (string) having grid elements separated by spaces    print_ = True, # Print results to console    show_non_max = True, # When printing if to show all clusters, not just largest, as B, C, D, E... (chars from "cchars")    cchars = ['.'] + [chr(ii) for ii in range(ord('B'), ord('Z') + 1)], # Clusters-chars, these chars are used to show clusters from largest to smallest    one = None, # Value of "one" inside grid array, e.g. if you have grid with chars then one may be equal to "1" string. Defaults to 1 (for non-text) or "1" (for text).    offs = [0, +1, -1], # All offsets (angles) that need to be checked, "off" is such that grid[i + 1][j + off] corresponds to next row of grid[i][j]    debug = False, # If True, extra debug info is printed):    # Preparing        assert algo in [0, 1, 2], algo    if text:        grid = [l.strip().split() for l in grid.splitlines() if l.strip()]    if one is None:        one = 1 if not text else '1'    r, c = len(grid), len(grid[0])    sgrid = '\n'.join([''.join([str(grid[ii][jj]) for jj in range(c)]) for ii in range(r)])    mas, ones = [], [one] * max(c, r)        # ----------------- Simple Algorithm, O(N^5) Complexity -----------------            if algo == 0 or check:        ma = [[(0, 0, 0) for jj in range(c)] for ii in range(r)] # Array containing maximal answers, Lower-Right corners                for i in range(r):            for j in range(c):                if grid[i][j] != one:                    continue                for k in range(j + 1, c): # Ensure at least 2 ones along X                    if grid[i][k] != one:                        break                    for off in offs:                        for l in range(i + 1, r): # Ensure at least 2 ones along Y                            if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:                                l -= 1                                break                            ry, rx = l, k + off * (l - i)                            rv = (l + 1 - i, k + 1 - j, off)                            if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:                                ma[ry][rx] = rv                                        mas.append(ma)        ma = None                        # ----------------- Advanced Algorithm using Dynamic Programming, O(N^3) Complexity -----------------    if algo == 1 or check:        ma = [[(0, 0, 0) for jj in range(c)] for ii in range(r)] # Array containing maximal answers, Lower-Right corners                for off in offs:            d = [[(0, 0, 0) for jj in range(c)] for ii in range(c)]            for i in range(r):                f, d_ = 0, [[(0, 0, 0) for jj in range(c)] for ii in range(c)]                for j in range(c):                    if grid[i][j] != one:                        f = j + 1                        continue                    if f >= j:                        # Check that we have at least 2 ones along X                        continue                    df = [(0, 0, 0) for ii in range(c)]                    for k in range(j, -1, -1):                        t0 = d[j - off][max(0, k - off)] if 0 <= j - off < c and k - off < c else (0, 0, 0)                        if k >= f:                            t1 = (t0[0] + 1, t0[1], off) if t0 != (0, 0, 0) else (0, 0, 0)                            t2 = (1, j - k + 1, off)                            t0 = t1 if t1[0] * t1[1] >= t2[0] * t2[1] else t2                                                        # Ensure that we have at least 2 ones along Y                            t3 = t1 if t1[0] > 1 else (0, 0, 0)                            if k < j and t3[0] * t3[1] < df[k + 1][0] * df[k + 1][1]:                                t3 = df[k + 1]                            df[k] = t3                        else:                            t0 = d_[j][k + 1]                        if k < j and t0[0] * t0[1] < d_[j][k + 1][0] * d_[j][k + 1][1]:                            t0 = d_[j][k + 1]                        d_[j][k] = t0                    if ma[i][j][0] * ma[i][j][1] < df[f][0] * df[f][1]:                        ma[i][j] = df[f]                d = d_                        mas.append(ma)        ma = None            # ----------------- Simple-ListComp Algorithm using List Comprehension, O(N^5) Complexity -----------------            if algo == 2 or check:        ma = [            [                max([(0, 0, 0)] + [                    (h, w, off)                    for h in range(2, i + 2)                        for w in range(2, j + 2)                            for off in offs                    if all(                        cr[                            max(0, j + 1 - w - off * (h - 1 - icr)) :                            max(0, j + 1 - off * (h - 1 - icr))                        ] == ones[:w]                        for icr, cr in enumerate(grid[max(0, i + 1 - h) : i + 1])                    )                ], key = lambda e: e[0] * e[1])                for j in range(c)            ]            for i in range(r)        ]        mas.append(ma)        ma = None        # ----------------- Checking Correctness and Printing Results -----------------    if check:        # Check that we have same answers for all algorithms        masx = [[[cma[ii][jj][0] * cma[ii][jj][1] for jj in range(c)] for ii in range(r)] for cma in mas]        assert all([masx[0] == e for e in masx[1:]]), 'Maximums of algorithms differ!\n\n' + sgrid + '\n\n' + (            '\n\n'.join(['\n'.join([' '.join([str(e1).rjust(2) for e1 in e0]) for e0 in cma]) for cma in masx])        )    ma = mas[0 if not check else algo]    if print_:        cchars = ['.'] + [chr(ii) for ii in range(ord('B'), ord('Z') + 1)] # These chars are used to show clusters from largest to smallest        res = [[grid[ii][jj] for jj in range(c)] for ii in range(r)]        mac = [[ma[ii][jj] for jj in range(c)] for ii in range(r)]        processed = set()        sid = 0        for it in range(r * c):            sma = sorted(                [(mac[ii][jj] or (0, 0, 0)) + (ii, jj) for ii in range(r) for jj in range(c) if (ii, jj) not in processed],                key = lambda e: e[0] * e[1], reverse = True            )            if len(sma) == 0 or sma[0][0] * sma[0][1] <= 0:                break            maxv = sma[0]            if it == 0:                maxvf = maxv            processed.add((maxv[3], maxv[4]))            show = True            for trial in [True, False]:                for i in range(maxv[3] - maxv[0] + 1, maxv[3] + 1):                    for j in range(maxv[4] - maxv[1] + 1 - (maxv[3] - i) * maxv[2], maxv[4] + 1 - (maxv[3] - i) * maxv[2]):                        if trial:                            if mac[i][j] is None:                                show = False                                break                        elif show:                            res[i][j] = cchars[sid]                            mac[i][j] = None            if show:                sid += 1            if not show_non_max and it == 0:                break        res = '\n'.join([''.join([str(res[ii][jj]) for jj in range(c)]) for ii in range(r)])        print(            'Max:\nArea: ', maxvf[0] * maxvf[1], '\nSize Row,Col: ', (maxvf[0], maxvf[1]),            '\nLowerRight Row,Col: ', (maxvf[3], maxvf[4]), '\nAngle: ', ("-1", " 0", "+1")[maxvf[2] + 1], '\n', sep = ''        )        print(res)        if debug:            # Print all computed maximums, for debug purposes            for cma in [ma, mac]:                print('\n' + '\n'.join([' '.join([f'({e0[0]}, {e0[1]}, {("-1", " 0", "+1")[e0[2] + 1]})' for e0_ in e for e0 in (e0_ or ('-', '-', 0),)]) for e in cma]))        print(end = '-' * 28 + '\n')        return ma# ----------------- Testing -----------------def test():    # Iterating over text inputs or other ways of producing inputs    for s in [        """        1 1 0 0 0 1 0 1        1 1 1 0 1 1 1 1        1 0 0 0 1 0 1 1        0 0 1 0 1 0 1 1        1 1 1 1 0 0 1 1        0 0 1 1 1 1 1 0        0 1 0 0 1 0 1 1        """,        """        1 0 1 1 0 1 0 0        0 1 1 0 1 0 0 1        1 1 0 0 0 0 0 1        0 1 1 1 0 1 0 1        0 1 1 1 1 0 1 1        1 1 0 0 0 1 0 0        0 1 1 1 0 1 0 1        """,        """        0 1 1 0 1 0 1 1        0 0 1 1 0 0 0 1        0 0 0 1 1 0 1 0        1 1 0 0 1 1 1 0        0 1 1 0 0 1 1 0        0 0 1 0 1 0 1 1        1 0 0 1 0 0 0 0        0 1 1 0 1 1 0 0        """    ]:        solve(s, text = True)if __name__ == '__main__':    test()输出：Max:Area: 8Size Row,Col: (4, 2)LowerRight Row,Col: (4, 7)Angle:  0CC000101CC1011..100010..001010..1BBB00..00BBBDD0010010DD----------------------------Max:Area: 6Size Row,Col: (3, 2)LowerRight Row,Col: (2, 1)Angle: -110..01000..01001..0000010BBB01010BBB1011CC0001000CC10101----------------------------Max:Area: 12Size Row,Col: (6, 2)LowerRight Row,Col: (5, 7)Angle: +10..0101100..0001000..010BB00..100BB00..0001010..1001000001101100----------------------------

在网格 Python 中查找模式

1回答