This looks very hard to me. I wouldn't be surprised if it is NP-hard.
If I had to solve it in practice, my first thought would be to try to solve it using a SAT solver or an ILP solver. I outline below how you could do that.
Given $k$, let's figure out whether there is a way to solve this using $k$ groups. If we can do that, we can use binary search over $k$ to find the smallest $k$ for which a solution exists (e.g., try $k=1,2,4,8,\cdots$ to find the first power of two for which a solution exists, then use binary search to narrow down exactly the minimum workable value of $k$).
Solving with a SAT solver
To solve this with a SAT solver, we need to formulate the problem in terms of boolean variables. I suggest introducing boolean variables $x_{c,i,j}$, where $c$ ranges over cells (locations) in the original matrix, $1 \le i \le 12$, and $1 \le j \le k$. The intent is that $x_{\cdot,12,j}$ should represent the $j$th group, i.e., $x_{c,12,j}$ should be true iff the $j$th group puts a 1 in cell $c$.
We need to ensure that the groups cover all C's. This can be done with the following constraints (clauses):
- For each cell $c$ that contains a C, $x_{c,12,1} \lor \cdots \lor x_{c,12,k}$
We need to ensure that the groups don't cover any B. This can be done with the following constraints:
- For each cell $c$ that contains a B and each $i,j$, $\neg x_{c,i,j}$
We need to ensure that each group has at most 12 1's. This can be done as follows:
Finally, we need to ensure that each group is connected. This is the hardest, but can be done as follows. The idea is that we'll grow a group, starting from a single cell (say $c_0$) and then expanding it; then $x_{\cdot,i,j}$ will be true for all cells with a 1 that are at most Manhattan distance $\le i$ from cell $c_0$. This can be expressed in SAT as follows:
For each $j$, exactly one of $x_{\cdot,1,j}$ is true. This is a cardinality/pseudo-boolean constraint; see above for how to enforce it.
$x_{\cdot,i,j}$ contains at least as many cells as $x_{\cdot,i-1,j}$, i.e., for each $i,j,c$ with $i>1$, $x_{c,i-1,j} \implies x_{c,i,j}$.
$x_{\cdot,i,j}$ is grown from $x_{\cdot,i-1,j}$ by adding only neighbors of cells in $x_{\cdot,i-1,j}$, i.e., for each $i,j,c$ with $i>1$, we have
$$x_{c,i,j} \implies (x_{c,i-1,j} \lor x_{c_L,i-1,j} \lor x_{c_R,i-1,j} \lor x_{c_U,i-1,j} \lor x_{c_D,i-1,j})$$
where $c_L,c_R,c_U,c_D$ are the four cells that are adjacent to $c$.
It may be helpful to add the extra constraint that $x_{\cdot,i,j}$ has at most 12 true values, for each $i,j$.
Finally, take the conjunction of all of these constraints, hand them to an off-the-shelf SAT solver (I like Z3Py), and ask it whether it can find any satisfying assignment. If it can, then you have found a solution using $k$ groups. If it can't, then you know there is no solution using $k$ groups.
Solving with an ILP solver
Another option is to use an ILP solver. Cardinality constraints are easier to express in an ILP solver, and boolean constraints are slightly messier but can all be done (see Express boolean logic operations in zero-one integer linear programming (ILP)), so you could do this with ILP instead of SAT. I don't know which will be more effective. You could try both if necessary.
Here's how this looks, for your particular case. We have 0-or-1 integer variables $x_{c,i,j}$, i.e., they are all marked integer and we add inequalities $0 \le x_{c,i,j} \le 1$. Now let's walk through the constraints (linear inequalities).
We need to ensure that the groups cover all C's. This can be done with the following inequalities:
- For each cell $c$ that contains a C, $x_{c,12,1} + \cdots + x_{c,12,k} \ge 1$.
We need to ensure that the groups don't cover any B. This can be done with the following constraints:
- For each cell $c$ that contains a B and each $i,j$, $x_{c,i,j} = 0$.
We need to ensure that each group has at most 12 1's. This can be done as follows:
- $\sum_c x_{c,12,j} \le 12$
Finally, we need to ensure that each group is connected. Following a similar idea as before, this can be expressed as an ILP as follows:
For each $j$, $\sum_c x_{c,1,j} = 1$.
For each $i,j,c$ with $i>1$, $x_{c,i-1,j} \le x_{c,i,j}$.
For each $i,j,c$ with $i>1$, we have
$$x_{c,i,j} \le x_{c,i-1,j} + x_{c_L,i-1,j} + x_{c_R,i-1,j} + x_{c_U,i-1,j} + x_{c_D,i-1,j}$$
where $c_L,c_R,c_U,c_D$ are the four cells that are adjacent to $c$.
It may be helpful to add the extra constraint that $\sum_c x_{c,i,j} \le 12$, for each $i,j$.
Finally, take all of these linear inequalities, hand them to an off-the-shelf ILP solver (Gurobi?), and ask it whether it can find any solution. If it can, then you have found a solution using $k$ groups. If it can't, then you know there is no solution using $k$ groups.
