Поиск шаблона в сетке Python [дубликат]

Oct 30 2020

У меня случайно сгенерированная сетка, содержащая 0 и 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

Как я могу выполнить итерацию по сетке, чтобы найти самый большой кластер единиц , который равен или превышает 4 элемента (по строке и столбцу)?

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

Проблема в том, что я не могу понять, как это сделать в строках и столбцах и записать счетчик. Я прошел через сетку, но не знаю, как продвинуться дальше двух строк.

Например, в приведенном выше примере самый большой кластер - 8. В сетке есть еще несколько кластеров, но они имеют 4 элемента:

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

Код, который я пробовал:

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

Ответы

2 Arty Nov 01 2020 at 15:26

Я реализовал три алгоритма.

Первый алгоритм Simple, использующий простейший подход вложенных циклов, имеет O(N^5) временную сложность (где в нашем случае N- одна сторона входной сетки 10), для наших входов размером 10x10time O(10^5)вполне нормально. Algo идентификатор в коде algo = 0. Если вы просто хотите увидеть этот алгоритм, перейдите к строке ------ Simple Algorithmвнутри кода.

Второй алгоритм Advanced, используя подход динамического программирования , его сложность O(N^3)намного быстрее, чем первый алгоритм. Algo идентификатор в коде algo = 1. Перейти к строке ------- Advanced Algorithmвнутри кода.

Третий алгоритм, который Simple-ListCompя реализовал просто для развлечения, он почти такой же, как Simpleи та же O(N^5)сложность, но с использованием понимания списков Python вместо обычных циклов, поэтому он короче, а также немного медленнее, потому что не использует некоторые оптимизации. Algo идентификатор в коде algo = 2. Перейдите к строке ------- Simple-ListComp Algorithmвнутри кода, чтобы увидеть алгоритм.

Остальной код, помимо алгоритмов, реализует проверку правильности результатов (двойная проверка между алгоритмами), печать результатов, создание текстовых вводов. Код разделен на функцию решения задачи и функцию solve()тестирования test(). solve()Функция имеет много аргументов, позволяющих настроить поведение функции.

Все основные строки кода задокументированы комментариями, прочтите их, чтобы узнать, как использовать код. В основном, если sпеременная содержит многострочный текст с элементами сетки, как и в вашем вопросе, вы просто запускаете, solve(s, text = True)и он решает задачу и печатает результаты. Также вы можете выбрать алгоритм из двух версий (0 (простой) и 1 (расширенный) и 2 (Simple-ListComp)), указав следующие аргументы для функции решения algo = 0, check = False(здесь 0 для алгоритма 0). Посмотрите на test()тело функции, чтобы увидеть простейший пример использования.

Алгоритмы вывода на консоль по умолчанию все кластеры, от самых больших до самых маленьких, по величине обозначается .символом, остальное по B, C, D, ..., Zсимволы. Вы можете установить аргумент show_non_max = Falseв функции решения, если хотите, чтобы отображался только первый (самый большой) кластер.