Thx a lot for every man and women for tests.

Try this:

4 4
1111
1110
1100
1000

The answer:
1110
1101
1011
0111

My code gives right answer for this test, but still got WA8.

My algo:
1) find any perfect match (I use kuhn algorithm). If there no perfect match print unary matrix and quit.

2) for every i-monster,  remove  edge (i, match(i)), and try make alternate path for i. save result in d[] array,  and restore edge (i, match(i)) .

3) We can select (i,j) edge  only if  Mij = true AND     (i,j) edge in perfect match, or j is free vertex,  or  d[ match( j ) ] is true.

Can give some tests ?

Test:
6 7
1111000
1110000
1100000
1000100
0000110
0000110

WA8 answer:
0000111
0001111
0011111
0111011
1111001
1111001