Проверьте шаблон рекурсивно

Question

* Заметьте, я называю вещь матрицей, но это не так, это просто набор из 1 и нулей

Предположим, у вас есть матрица, которая всегда квадратная (n x n). Можно ли определить, существует ли один столбец / строка / диагональ, так что каждый элемент равен 1.

Взять, к примеру, приведенную ниже матрицу (True):

1 0 0
1 1 0
0 0 1

Другой пример (True):

1 1 1
0 0 0
0 1 0

И, наконец, один без решения (Ложь):

0 1 1
1 0 0
0 0 0

Обратите внимание на диагональ, заполненную цифрами 1. Правило есть или есть решение, или нет решения. В матрице может быть любое количество единиц или нулей. Все, что мне действительно нужно сделать, это, если у вас есть (n x n), тогда должна быть строка / столбец / диагональ с n одинаковыми элементами.

Если это невозможно с рекурсиями, пожалуйста, дайте мне знать, что является лучшим и наиболее эффективным методом. Большое спасибо, я застрял на этом в течение нескольких часов, поэтому любая помощь приветствуется (если бы вы могли опубликовать образцы, это было бы здорово).

РЕДАКТИРОВАТЬ
Это одно из решений, которое я придумала, но через некоторое время оно становится действительно сложным.

Возьмите первый пример, который я дал, и объедините все строки вместе, чтобы вы получили:

1 0 0, 1 1 0, 0 0 1
Затем добавьте нули между строками, чтобы получить:
1 0 0 0, 1 1 0 0, 0 0 1 0

Теперь, если вы посмотрите внимательно, вы увидите, что расстояния между единицами, которые образуют решение, равны. Хотя я не знаю, как это можно реализовать.

Answer 1

В поисках элегантного решения я придумал следующее:

class LineOfOnesChecker(object):

    _DIAG_INDICES = (lambda i: i, lambda i: -i - 1)

    def __init__(self, matrix):
        self._matrix = matrix
        self._len_range = range(len(self._matrix))

    def has_any(self):
        return self.has_row() or self.has_col() or self.has_diag()

    def has_row(self):
        return any(all(elem == 1 for elem in row)
                   for row in self._matrix)

    def has_col(self):
        return any(all(self._matrix[i][j] == 1 for i in self._len_range)
                   for j in self._len_range)

    def has_diag(self):
        return any(all(self._matrix[transf(i)][i] == 1 for i in self._len_range)
                   for transf in self._DIAG_INDICES)

Использование:

print LineOfOnesChecker(matrix).has_any()

Answer 2

Исходя из того, что я понимаю в этой проблеме, вам просто нужно проверить, состоит ли какая-либо строка, столбец или диагональ целиком из «1».Это можно сделать очень легко, используя all в Python, поэтому я не понимаю, почему вы хотите сделать это рекурсивно.

Более очевидное (на мой взгляд) решение - что-то вроде этого:

#! /usr/bin/env python
boards=[
        ((0,1,0),(1,0,1),(0,1,0)),
        ((1,1,1),(0,0,0),(0,0,0)),
        ((0,0,0),(1,1,1),(0,0,0)),
        ((0,0,0),(0,0,0),(1,1,1)),
        ((1,0,0),(1,0,0),(1,0,0)),
        ((0,1,0),(0,1,0),(0,1,0)),
        ((0,0,1),(0,0,1),(0,0,1)),
        ((1,0,0),(0,1,0),(0,0,1)),
        ((0,0,1),(0,1,0),(1,0,0)),
        ((0,0,0),(0,0,0),(0,0,0))
]

def check(board):
        for row in board:
                if all(row):
                        return True
        for col in xrange(len(board)):
                vector=[board[row][col] for row in xrange(len(board))]
                if all(vector):
                        return True
        diag1=[board[i][i] for i in xrange(len(board))]
        if all(diag1):
                return True

        diag2=[board[i][i] for i in xrange(len(board)-1,-1,-1)]
        if all(diag2):
                return True

        return False

if __name__=='__main__':
        for board in boards:
                if check(board):
                        print "Yes"
                else:
                        print "No"

Answer 3

Вы можете иметь список n 1 и делать 'AND' для ваших наборов диагональных элементов, элементов строки и элементов столбца и, если они есть, операции ANDв результате ИСТИНА, тогда у вас есть действительный шаблон.

import sys
matrix = [[1,0,1],[1,0,1],[1,0,1]]
transpose = zip(*matrix)
diagonal1 =  []
for n,elem in enumerate(matrix):
    diagonal1.append(elem[n])
diagonal2 = []
for n,elem in enumerate(transpose):
    diagonal2.append(elem[n])
for row in matrix:
    if reduce(lambda x,y: x and y, row):
        print True
        sys.exit()
for row in transpose:
    if reduce(lambda x,y: x and y, row):
        print True
        sys.exit()
if (reduce(lambda x,y: x and y, diagonal1) or reduce(lambda x, y: x and y, diagonal2)):
    print True
    sys.exit()