Распознавание фигур в массиве 2d

Question

Я хочу распознавать двумерные фигуры (например, цифры тетриса, где 1 означает заполненный блок, а 0 - пустую плоскость) в двумерном массиве (случайным образом выделены 0 и 1). Есть ли общие подходы? Первая идея состоит в том, чтобы выполнить итерацию по исходному массиву, предполагая, что A [i, j] является исходной точкой ожидаемой фигуры, и сравнить полученную фигуру с эталонной.

Для массивов 100x100 и 10x10 это займет (100-10) * (100-10) = 8100 операций, и это означает, что O = n ^ 2 в целом, потому что я могу исправить много цифр? Конечно, кеширование может быть применено, и мы можем пытаться выполнять итерации только по «грязным» разделам ...

Однако я полагаю, что лучшие решения должны существовать. Кто-то может указать на них?

Answer 1

Общий подход, который я выбрал бы, также был бы равен O (n ^ 2), но, похоже, он больше зависит от количества цифр (полиомино), чем от количества блоков.

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

Полагаю, очень важно, известно ли число фигур в сетке заранее или нет.