Maximum Number of Patterns That Fit in a Space

Question

Suppose that you have a boolean, n-by-m, randomly-initialized array A, and suppose that you have a boolean, p-by-q, randomly-initialized array B, where p <= n and q <= m.

I want to know the maximum number of Bs that fit in A: I say that B fits in A if not (A[k + i, l + j] and B[i, j]) is true for every 0 <= i < p and every 0 <= j < q, where 0 <= k < n - p and 0 <= l < m - q.

In simpler words, I have a pattern and a map with obstructions, and I want to know the maximum number of patterns that fit in said map. I use the convention that true and false represent occupied and unoccupied space, respectively.

I am currently tackling this problem via recursion, but it is extraordinarily inefficient. I wonder if there is a better approach. I would appreciate even a reference.

Edit 1: I am interested in the maximum number of non-overlapping Bs.

Edit 2: Let A be the following array:

Let B be the following array:

Notice that I let B and its center be of different colors for visualization purposes only.

Then I can fit Bs into A in the following two ways:

In the first image, I was able to fit six Bs. However, in the second image, I was able to fit nine. I am interested in the maximum number.

Answer 1

The most straight-forward approach I can think of would be worst-case O(mnpq). Think of matrix B as a template which lays on top of matrix A. For each position x,y in A where B can be placed with it's top left corner on that position (x,y) so that all of matrix B is contained within A (there are (m-p)(n-q) of these positions), check that for each 0<=i<p and 0<=j<q, B[i][j] and A[x+i][y+j] are not both 1. Count the number of locations where this occurs. This code would use four nested if loops, and avoid recursion altogether.

If A happens to be sparse (few positions are true), it would be more efficient to work backwards, noting locations where B cannot be placed. Begin with a matrix C of size A initialized to true. Scan A for all positions where A[x][y] is true, and note values where if the upper-left corner of B were to be placed, a true in B would collide with a true in A. Set all values of C where this occurs equal to false. Once completed, summing matrix C will provide you with the number of locations where no collisions occur.