[Python] 隣接したセルの数を求める

問題

1または0から成る行列がある。あるセルの上下左右斜め8方向を見る時、同じ数字であればそのセル同士は互いに隣接していて、集団を形成しているとする。互いに隣接している１から成る集団の中で、最も含まれるセルが多い集団を考えた場合、いくつのセルが含まれるかを答えなさい。

例

下の行列であれば、隣接している1のセルの中で最大の集団は11個のセルを含んでいる。

$$ \left( \begin{array}{ccccc} 1&1&0&0&0 \\ 0&1&1&0&1 \\ 0&0&0&1&1 \\ 1&0&0&1&1 \\ 0&1&0&1&1 \end{array} \right) $$

回答

def get_val(A, i, j, L, H):
    if i < 0 or i >= L or j < 0 or j >= H:
        return 0
    return A[i][j]

def find_max_block(A, r, c, L, H, size):
    global maxsize
    global cntarr
    if r >= L or c >= H:
        return
    # 訪問済みのフラグを立てる。
    cntarr[r][c] = 1
    size += 1
    if size > maxsize:
        maxsize = size
    # 8方向調べる。
    direction = [[-1, 0], [-1, -1], [0, -1], [1, -1], [1, 0], [1, 1], [0, 1], [-1, 1]]
    for i in range(7):
        new_i = r + direction[i][0]
        new_j = c + direction[i][1]
        val = get_val(A, new_i, new_j, L, H)
        if val == 1 and cntarr[new_i][new_j] == 0:
            find_max_block(A, new_i, new_j, L, H, size)


def get_max_once(A, rmax, colmax):
    global maxsize
    global size
    global cntarr
    for i in range(rmax):
        for j in range(colmax):
            if A[i][j] == 1:
                find_max_block(A, i, j, rmax, colmax, 0)
    return maxsize


zarr = [[1, 1, 0, 0, 0],
        [0, 1, 1, 0, 1],
        [0, 0, 0, 1, 1],
        [1, 0, 0, 1, 1],
        [0, 1, 0, 1, 1]]
rmax = 5
colmax = 5
maxsize = 0
size = 0
cntarr = [colmax * [0] for _ in range(rmax)]

ans = get_max_once(zarr, rmax, colmax)
print(f'Number of maximum 1s are {ans}')