Рассмотрим двумерную сетку (обычную решетку на плоскости). Для моих целей схема pattern или - это присвоение чисел 1 и 2 некоторому связанному подмножеству точек сетки. Например, ниже показаны три отдельные схемы:
.......1.....1....
.222...2.....12...
.111...2.....2....
.222...22...12211.
.......1....11.1..
Я говорю, что маленький шаблон соответствует большому, если маленький можно повернуть или отразить так, чтобы все его числа были меньше, чем числа в большем. Например, рассмотрим этот шаблон:
......
.1212.
....2.
......
Он НЕ соответствует крайнему левому расположению, указанному выше, потому что его нельзя повернуть или отразить, чтобы поместиться в квадрат 3х3. Он соответствует среднему расположению, потому что его можно вращать и отражать, чтобы разместить под ним. Однако он НЕ соответствует крайнему правому расположению, поскольку, несмотря на то, что он повернут или отражен для соответствия крайнему правому расположению, цифры на маленьком рисунке больше, чем на большом расположении. (Если какой-либо из моих примеров неясен или вам нужна дополнительная информация, просто спросите об этом в области комментариев. Некоторые пояснения заранее: рисунок не может быть растянут и не может быть повернут, поэтому он является диагональным относительно сетки Это означает, что всего четыре поворота и четыре отражения, каждое из которых можно перевести.)
Меня интересуют следующие вопросы:
Как быстро проверить, соответствует ли маленький шаблон большому расположению?
Предположим, у меня много маленьких паттернов. Можно ли как-то предварительно обработать их, чтобы быстро определить, соответствует ли хотя бы один из них соглашению?
Полагаю, было бы неплохо, если бы решение решало более общую проблему (например, произвольные числа - не только 1 и 2 - или допускает несвязные формы), но я действительно беспокоюсь только о случае выше. Спасибо.