As for a 01-matrix MMM of size n×mntimes mn×m, an index set SSS of the matrix is considered good if following two conditions are satisfied: Mu,v=0M_{u,v}=0Mu,v=0, for all (u,v)∈S(u,v)in S(u,v)∈S For each entry Mi,j=0M_{i,j}=0Mi,j=0, there exists an index (u,v)∈S(u,v)in S(u,v)∈S satisfying the following two conditions at the same time: ·i=ui=ui=uorj=vj=vj=v ·Mx,y=0M_{x,y}=0Mx,y=0 for all x,yx,yx,y such that ≤0(x-i)(x-u)le 0≤0 and ≤0(y-j)(y-v)le 0≤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 2cnt22^{cnt_2}2cnt2 replacing schemes, where cnt2cnt_2cnt2 denotes the number of 2 entries in the given matrix.
As for a 01-matrix(whose entries are all either 0 or 1, similarly hereinafter) MMM of size n×mntimes mn×m, an index set SSS of the matrix is considered good if following two conditions are satisfied: Mu,v=0M_{u,v}=0Mu,v=0, for all (u,v)∈S(u,v)in S(u,v)∈S For each entry Mi,j=0(1≤i≤n,1≤j≤m)M_{i,j}=0(1le i le n,1le jle m)Mi,j=0(1≤i≤n,1≤j≤m), there exists an index (u,v)∈S(u,v)in S(u,v)∈S satisfying the following two conditions at the same time: · i=ui=ui=u or j=vj=vj=v · Mx,y=0M_{x,y}=0Mx,y=0 for all x,yx,yx,y such that (x−i)(x−u)≤0(x-i)(x-u)le 0(x−i)(x−u)≤0 and (y−j)(y−v)≤0(y-j)(y-v)le 0(y−j)(y−v)≤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 2cnt22^{cnt_2}2cnt2 replacing schemes, where cnt2cnt_2cnt2 denotes the number of 2 entries in the given matrix.
