Tìm một mẫu trong Grid Python [bản sao]

Question

Tôi có lưới được tạo ngẫu nhiên chứa 0 và 1:

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

Làm cách nào để tôi có thể lặp qua lưới để tìm cụm 1s lớn nhất , bằng hoặc lớn hơn 4 mục (trên hàng và cột)?

Tôi giả sử tôi cần giữ số lượng của mỗi cụm tìm thấy trong khi lặp lại và đếm hơn 4 mục của nó, ghi lại và đếm trong một danh sách và sau đó tìm số lớn nhất.

Vấn đề là tôi không thể tìm ra cách làm như vậy trên cả hàng và cột và ghi lại số lượng. Tôi đã lặp lại qua lưới nhưng không chắc làm thế nào để di chuyển xa hơn hai hàng.

Ví dụ trong ví dụ trên, cụm lớn nhất là 8. Có một số cụm khác trong lưới, nhưng chúng có 4 phần tử:

AA 0 0 0 1 0 1
A A 1 0 1 1 1 1
1 0 0 0 1 0 1 1
0 0 1 0 1 0 1 1
1 1 BB 0 0 1 1
0 0 BB 1 1 1 0
0 1 0 0 1 0 1 1

Mã tôi đã thử:

rectcount = []
for row in range(len(grid)):
    for num in range(len(grid[row])):

    # count = 0
        try:

            # if grid[row][num] == 1:
                # if grid[row][num] == grid[row][num + 1] == grid[row + 1][num] == grid[row + 1][num + 1]:
                    # count += 1

            if grid[row][num] == grid[row][num + 1]:
                if grid[row + 1][num] == grid[row][num + 1]:
                    count += 1

                # if grid[row][num] == grid[row][num + 1] and grid[row][num] == grid[row + 1][num]:
                    # count += 1
                else:
                    count = 0

            if grid[row][num] == grid[row + 1][num]:
                count += 1
        except:
            pass

Answer 1

Tôi đã triển khai ba thuật toán.

Thuật toán đầu tiên là Simple, sử dụng cách tiếp cận dễ dàng nhất của các vòng lặp lồng nhau, nó có O(N^5) độ phức tạp về thời gian (trong đó Nmột mặt của lưới đầu vào, 10đối với trường hợp của chúng ta), đối với các đầu vào có kích thước 10x10thời gian O(10^5)là khá ổn. Id Algo trong mã là algo = 0. Nếu bạn chỉ muốn xem thuật toán này, hãy nhảy đến dòng ------ Simple Algorithmbên trong mã.

Thuật toán thứ hai là Advanced, sử dụng cách tiếp cận Lập trình động , độ phức tạp của nó O(N^3)nhanh hơn nhiều so với thuật toán thứ nhất. Id Algo trong mã là algo = 1. Chuyển đến dòng ------- Advanced Algorithmbên trong mã.

Thuật toán thứ ba Simple-ListComptôi đã triển khai chỉ để giải trí, nó gần giống như Simple, cùng O(N^5)độ phức tạp, nhưng sử dụng khả năng hiểu danh sách của Python thay vì các vòng lặp thông thường, đó là lý do tại sao nó ngắn hơn, cũng chậm hơn một chút vì không sử dụng một số tối ưu hóa. Id Algo trong mã là algo = 2. Chuyển đến dòng ------- Simple-ListComp Algorithmbên trong mã để xem thuật toán.

Phần còn lại của mã, ngoài các thuật toán, thực hiện kiểm tra tính đúng đắn của kết quả (kiểm tra hai lần giữa các thuật toán), in kết quả, tạo đầu vào văn bản. Mã được chia thành chức năng giải quyết nhiệm vụ solve()và chức năng kiểm tra test(). solve()hàm có nhiều đối số để cho phép cấu hình hành vi của hàm.

Tất cả các dòng mã chính được ghi lại bằng các nhận xét, hãy đọc chúng để tìm hiểu cách sử dụng mã. Về cơ bản, nếu sbiến chứa văn bản nhiều dòng với các phần tử lưới, giống như trong câu hỏi của bạn, bạn chỉ cần chạy solve(s, text = True)và nó sẽ giải quyết công việc và in kết quả. Ngoài ra, bạn có thể chọn thuật toán trong số hai phiên bản (0 (Đơn giản) và 1 (Nâng cao) và 2 (Đơn giản-ListComp)) bằng cách đưa ra các đối số tiếp theo để giải hàm algo = 0, check = False(ở đây là 0 cho bí danh 0). Nhìn vào test()phần thân hàm để xem ví dụ đơn giản nhất về cách sử dụng.

Các thuật toán đầu ra để điều khiển theo mặc định tất cả các cụm, từ lớn nhất đến nhỏ nhất, lớn nhất được biểu thị bằng .biểu tượng, phần còn lại bởi B, C, D, ..., Zcác biểu tượng. Bạn có thể đặt đối số show_non_max = Falsetrong hàm giải quyết nếu bạn muốn chỉ cụm đầu tiên (lớn nhất) được hiển thị.

Tôi sẽ giải thích thuật toán đơn giản:

1. Về cơ bản, thuật toán làm gì - nó tìm kiếm thông qua tất cả các 1shình chữ nhật góc cạnh có thể có và lưu trữ thông tin về tối đa của chúng vào mamảng 2D. Top-leftđiểm của hình chữ nhật đó là (i, j), top-right- (i, k), bottom-left- (l, j + angle_offset), bottom-right- (l, k + angle_offset), cả 4 góc, đó là lý do tại sao chúng ta có rất nhiều vòng lặp.
2. Trong hai vòng ngoài i(hàng), j(cột) chúng ta lặp trên toàn bộ lưới, (i, j)vị trí này sẽ là top-leftđiểm của 1shình chữ nhật, chúng ta cần lặp lại toàn bộ lưới vì tất cả các 1shình chữ nhật có thể có top-leftở bất kỳ (row, col)điểm nào của toàn bộ lưới. Khi bắt đầu jvòng lặp, chúng tôi kiểm tra rằng lưới tại (i, j)vị trí phải luôn chứa 1bởi vì bên trong các vòng lặp, chúng tôi chỉ tìm kiếm tất cả các hình chữ nhật 1s.
3. kvòng lặp lặp qua tất cả các top-rightvị trí có thể có (i, k)của 1shình chữ nhật. Chúng ta nên thoát ra khỏi vòng lặp nếu (i, k)bằng với 0vì không có điểm nào để mở rộng kthêm về bên phải vì hình chữ nhật như vậy sẽ luôn chứa 0.
4. Trong các vòng trước, chúng tôi đã cố định top-leftvà top-rightcác góc của hình chữ nhật. Bây giờ chúng ta cần tìm kiếm hai góc dưới cùng. Để làm được điều đó, chúng ta cần mở rộng hình chữ nhật xuống dưới ở các góc khác nhau cho đến khi đạt được đầu tiên 0.
5. offvòng lặp cố gắng kéo dài hình chữ nhật xuống dưới ở tất cả các góc có thể ( 0(thẳng đứng), +1( 45độ dịch chuyển sang phải từ trên xuống dưới), -1( -45độ)), offvề cơ bản là số như vậy grid[y][x]là "trên" (tương ứng với Y) grid[y + 1][x + off].
6. lcố gắng kéo dài hình chữ nhật xuống dưới ( Ytheo hướng) ở các góc khác nhau off. Nó được kéo dài cho đến lần đầu tiên 0bởi vì nó không thể được kéo dài thêm sau đó (vì mỗi hình chữ nhật như vậy sẽ chứa sẵn 0).
7. lVòng lặp bên trong có if grid[l][max(0, j + off * (l - i)) : min(k + 1 + off * (l - i), c)] != ones[:k - j + 1]:điều kiện, về cơ bản, điều này ifcó nghĩa là để kiểm tra xem hàng cuối cùng của hình chữ nhật có chứa tất cả 1hay không nếu điều này ifxảy ra khỏi vòng lặp. Điều kiện này so sánh hai phần listkhông bằng nhau. Hàng cuối cùng của hình chữ nhật kéo dài từ điểm (l, j + angle_offset)(biểu thức max(0, j + off * (l - i)), giới hạn tối đa là 0 <= X) đến điểm (l, k + angle_offset)(biểu thức min(k + 1 + off * (l - i), c), giới hạn tối thiểu là X < c).
8. Bên trong lvòng có dòng khác, ry, rx = l, k + off * (l - i)tính bottom-rightchỉ của hình chữ nhật (ry, rx)đó là (l, k + angle_offset), này (ry, rx)vị trí được sử dụng để lưu trữ tìm thấy bên trong tối đa mamảng, mảng này lưu trữ tất cả tối đa tìm thấy hình chữ nhật, ma[ry][rx]chứa thông tin về hình chữ nhật có bottom-rightvào thời điểm (ry, rx).
9. rv = (l + 1 - i, k + 1 - j, off)dòng tính toán ứng viên mới có thể có cho ma[ry][rx]mục nhập mảng, có thể vì ma[ry][rx]được cập nhật chỉ khi ứng viên mới có diện tích lớn hơn 1s. Ở đây rv[0]giá trị bên trong rvbộ giá trị chứa heighthình chữ nhật đó, rv[1]chứa widthhình chữ nhật đó ( widthbằng chiều dài của hàng dưới cùng của hình chữ nhật), rv[2]chứa góc của hình chữ nhật đó.
10. Điều kiện if rv[0] * rv[1] > ma[ry][rx][0] * ma[ry][rx][1]:và phần thân của nó chỉ kiểm tra xem rvvùng có lớn hơn mức tối đa hiện tại bên trong mảng ma[ry][rx]hay không và nếu nó lớn hơn thì mục nhập mảng này được cập nhật ( ma[ry][rx] = rv). Tôi sẽ nhắc rằng ma[ry][rx]chứa thông tin (width, height, angle)về hình chữ nhật có diện tích cực đại được tìm thấy hiện tại có bottom-rightđiểm tại (ry, rx)và có các điểm này width, heightvà angle.
11. Làm xong! Mảng sau khi chạy thuật toán machứa thông tin về tất cả các (cụm) hình chữ nhật góc có diện tích tối đa 1sđể tất cả các cụm có thể được khôi phục và in sau đó ra bảng điều khiển. Phần lớn nhất của tất cả các-nhóm như vậy 1sbằng một số rv0 = ma[ry0][rx0], chỉ cần lặp lại một lần qua tất cả các phần tử của mavà tìm điểm (ry0, rx0)đó sao cho ma[ry0][rx0][0] * ma[ry0][rx0][1](diện tích) là cực đại. Khi đó cụm lớn nhất sẽ có bottom-rightđiểm (ry0, rx0), bottom-leftđiểm (ry0, rx0 - rv0[1] + 1), top-rightđiểm (ry0 - rv0[0] + 1, rx0 - rv0[2] * (rv0[0] - 1)), top-leftđiểm (ry0 - rv0[0] + 1, rx0 - rv0[1] + 1 - rv0[2] * (rv0[0] - 1))(ở đây rv0[2] * (rv0[0] - 1)chỉ là độ lệch góc, tức là hàng đầu tiên được dịch chuyển bao nhiêu Xso với hàng cuối cùng của hình chữ nhật).

Hãy thử nó trực tuyến!

# ----------------- 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()

Đầu ra:

Max:
Area: 8
Size Row,Col: (4, 2)
LowerRight Row,Col: (4, 7)
Angle:  0

CC000101
CC1011..
100010..
001010..
1BBB00..
00BBBDD0
010010DD
----------------------------
Max:
Area: 6
Size Row,Col: (3, 2)
LowerRight Row,Col: (2, 1)
Angle: -1

10..0100
0..01001
..000001
0BBB0101
0BBB1011
CC000100
0CC10101
----------------------------
Max:
Area: 12
Size Row,Col: (6, 2)
LowerRight Row,Col: (5, 7)
Angle: +1

0..01011
00..0001
000..010
BB00..10
0BB00..0
001010..
10010000
01101100
----------------------------