#java #python #algorithm #dynamic-programming
#java #python #алгоритм #динамическое программирование
Вопрос:
Как мне найти все возможные места размещения определенного полиомино в сетке? Например,
просто взглянув на T tetromino без преобразований (извините за навыки рисования MS): 
Каков самый быстрый способ выяснить, сколькими способами я могу разместить этот tetromino только на прямоугольной сетке, подобной первой сетке? Должен ли быть другой метод для нерегулярных сеток, таких как Grid 2? Это единственный способ перебрать его, просто поместив его в каждую ячейку и проверив, находится ли все тетромино в пределах границ?
Комментарии:
1. Для первой сетки T-тетромино в показанной вами ориентации может поместиться в 42 местах: верхняя левая ячейка может находиться в любом столбце, кроме крайнего правого, и в любой строке, кроме двух внизу, и это определяет, куда идет остальная часть. Аналогично для любой другой прямоугольной сетки. Что касается сеток, таких как вторая, ничего не зная о неравномерности сетки, вы ничего не можете сделать, кроме как проверить все местоположения и посмотреть, где подходит полиомино.
2. @LukeWoodward я предполагаю, что OP ищет что-то вроде 2D-версии Knuth-Morris-Pratt