409138: GYM103446 C Strange Matrices

As for a 01-matrix(whose entries are all either 0 or 1, similarly hereinafter) $$$M$$$ of size $$$n\times m$$$, an index set $$$S$$$ of the matrix is considered good if following two conditions are satisfied:

1. $$$M_{u,v}=0$$$, for all $$$(u,v)\in S$$$
2. For each entry $$$M_{i,j}=0(1\le i \le n,1\le j\le m)$$$, there exists an index $$$(u,v)\in S$$$ satisfying the following two conditions at the same time:
   • $$$i=u$$$ or $$$j=v$$$
   • $$$M_{x,y}=0$$$ for all $$$x,y$$$ such that $$$(x-i)(x-u)\le 0$$$ and $$$(y-j)(y-v)\le 0$$$

Moreover, the value of a 01-matrix is the minimum size among all of its good index sets.

Now given a 012-matrix, you should replace all the 2 entries to 0 or 1, and determine the minimum possible value among all replacing schemes. As can be seen, there are totally $$$2^{cnt_2}$$$ replacing schemes, where $$$cnt_2$$$ denotes the number of 2 entries in the given matrix.

The first line contains two integers $$$n,m \, (1\le n,m \le 8)$$$, denoting the size of given 012-matrix.

Following $$$n$$$ lines each contains one 012-string of length $$$m$$$, where the $$$j$$$-th character in the $$$i$$$-th line among the $$$n$$$ lines denotes entry $$$M_{i,j}$$$.

Output one line containing one integer, denoting the minimum possible value after replacing.

3 7
0001101
0201020
0001101

3

One possible replacing scheme is: $$$$$$ \begin{aligned} 0001101 \\ 0101000 \\ 0001101 \end{aligned} $$$$$$ One possible good set of the minimum size is $$$\{(1,1),(2,6),(3,3)\}$$$