Матричный алгоритм поиска дырок в матрице сопоставления

Question

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

Например: Матрица A:

[1,0,1,1,1]
[1,0,0,1,1]
[1,0,0,1,1]
[1,1,0,0,1]
[1,1,1,1,1]

Матрица B:

[1,0]
[1,0]
[1,1]

Есть 2 места, где Матрица B могла бы поместиться в Матрице A - (0,1) и (1,2).Я мог бы сделать это методом грубой силы (разверните матрицу B, чтобы соответствовать размеру матрицы A, переверните матрицу A и «И» их вместе. Сдвиньте матрицу B вправо, затем вниз, пока не будет представлена ​​каждая возможная позиция фигуры).Интуитивно кажется, что должен быть более эффективный способ сделать то же самое, используя некоторую матричную библиотеку или формулу.

Спасибо

Answer 1

Вы можете попробовать использовать алгоритм Baker-Bird (скажем, это расширение алгоритма KMP в двух измерениях).Пожалуйста, поищите в этой теме, где вы можете найти еще несколько объяснений: 2D-сравнение строк: алгоритм Бейкера-Берда