Проверка чисел в матрице. python

Question

На вход программе подается двумерный список размерностью 5 х 5 элементов, состоящий из нулей и в некоторых позициях единицы. Требуется проверить, не касаются ли единицы друг друга по горизонтали, вертикали и диагонали. То есть, вокруг каждой единицы должны быть нули. Если проверка проходит вывести на экран "ДА", иначе "НЕТ".

мне нейросеть предложила такой вариант решения моей задачи. но как бы я не задавал вопрос, желаемого ответа так и не получил.

def check_matrix(matrix):
    # Размер матрицы
    n = len(matrix)
    
    # Функция для проверки соседних элементов
    def is_isolated(i, j):
        # Проверяем все соседние ячейки
        for di in [-1, 0, 1]:
            for dj in [-1, 0, 1]:
                # Пропускаем саму ячейку
                if di == 0 and dj == 0:
                    continue
                # Координаты соседней ячейки
                ni, nj = i + di, j + dj
                # Проверяем границы матрицы и наличие единицы в соседней ячейке
                if 0 <= ni < n and 0 <= nj < n and matrix[ni][nj] == 1:
                    return False
        return True

    # Проходим по всей матрице
    for i in range(n):
        for j in range(n):
            # Если нашли единицу, проверяем ее окружение
            if matrix[i][j] == 1:
                if not is_isolated(i, j):
                    return "НЕТ"
    
    return "ДА"

# Пример использования
matrix = [
    [0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

print(check_matrix(matrix))

for di in [-1, 0, 1]:
            for dj in [-1, 0, 1]:

что значит эта строка, и какое отношение она имеет к i и j?

Answer 1

d - сокращение от delta. di - это изменение индекса i, dj - аналогично для j.

Эти два цикла олицетворяют квадрат вокруг точки 0,0, а после сдвига - вокруг i,j.

Визуально кажется, что код верный если матрица обязательно квадратная. Если не квадратная, то его легко изменить. Возврат строк не радует, а так, должно работать.

Answer 2

Нет нужды делать проверку всех соседей элемента - раз мы итерируем по всей матрице с начала и до конца, то достаточно проверять элемент справа, снизу и вправо вниз и вправо вверх по диагонали. Можно делать проверку на границу матрицы, а можно, например, сначала добавить нулевых элементов справа и снизу (padding), и обойтись без проверки граничных значений. как-то так:

def check_m(matrix: list)-> bool:
    w = len(matrix[0])
    h = len(matrix)
    matrix.append([0 for x in range(h)])
    for x in matrix:
        x+=[0]
    for i in range(w):
        for j in range(h):
            if matrix[i][j]==1:
                if matrix[i+1][j]==1 or matrix[i][j+1]==1 or matrix[i+1][j+1]==1 or matrix[i+1][j-1]:
                    return False
    return True
print(check_m(matrix))

Answer 3

Не ответ на вопрос, но забавное решение с минимумом if и компактное:

def check_matrix(matrix):
    n = len(matrix)
    for di, dj in ((-1, 1), (0, 1), (1, 1), (1, 0)): 
        ri = range(max(0, -di), min(n, n - di))
        rj = range(n - dj)
        for i in ri:
            for j in rj:
                if matrix[i][j] == 1 == matrix[i + di][j + dj]:
                    return False
    return True

P.S. Для этой задачи хорошо подходит NumPy - там можно устроить свёртку с ядром, всё будет сделано в одну векторную операцию.

Ну в одну не получилось:

def check_matrix(matrix):
    m = np.array(matrix)
    m = m[:, :-1] + m[:, 1:]
    m = m[:-1, :] + m[1:, :]
    return (m > 1).any()

Answer 4

Вот решение as per @Stanislav Volodarskiy - конволюция с ядром средствами scipy:

import numpy as np
from scipy import signal
matrix1 = [
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0]
]
matrix2 = [
    [1, 0, 0, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

def check_w_conv(matrix) -> bool:
    return (signal.convolve2d(np.array(matrix), np.ones((2,2)))>1).any()

print(check_w_conv(matrix1))
print(check_w_conv(matrix2))

False
True

БЛОГ НА HUSL

Проверка чисел в матрице. python

Ответы (4 шт):