Fill Binary Matrix with Alternating Rectangles of 0 and 1

Given a M x N binary matrix, fill it with alternating rectangles of 0 and 1.


For example,


Input: 10 x 8 matrix

Output:

1   1   1   1   1   1   1   1
1   0   0   0   0   0   0   1
1   0   1   1   1   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   1   1   1   0   1
1   0   0   0   0   0   0   1
1   1   1   1   1   1   1   1

 


 

The idea is to fill the matrix by following the spiral order. All elements involved in each alternating run in spiral order are filled by either 0 or 1 based on input from last run. To maintain the spiral order four loops are used, each for top, right, bottom and left corner of the matrix.

C++

Download   Run Code

Output:

1   1   1   1   1   1   1   1
1   0   0   0   0   0   0   1
1   0   1   1   1   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   1   1   1   0   1
1   0   0   0   0   0   0   1
1   1   1   1   1   1   1   1

 

Another approach:

A M x N matrix has min(ceil(M/2), ceil(N/2)) rectangular cycles. A cycle is formed by ith row, (N-i+1)th column, (M-i+1)th row and ith column where i varies from 1 to min(ceil(M/2), ceil(N/2)). The idea is for each rectangular cycle, we associate a value to it. For outer cycle, the value will be 0, for second cycle, the value will be 1 and third cycle will have value 2 and so on.. Below figure shows 4 cycles in a 10 x 8 matrix marked by value 0 – 3.


0   0   0   0   0   0   0   0
0   1   1   1   1   1   1   0
0   1   2   2   2   2   1   0
0   1   2   3   3   2   1   0
0   1   2   3   3   2   1   0
0   1   2   3   3   2   1   0
0   1   2   3   3   2   1   0
0   1   2   2   2   2   1   0
0   1   1   1   1   1   1   0
0   0   0   0   0   0   0   0

Now depending upon weather the assigned value is odd or even for a matrix cell, we assign 0 or 1 to the output matrix.

C++

Download   Run Code

Output:

1   1   1   1   1   1   1   1
1   0   0   0   0   0   0   1
1   0   1   1   1   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   0   0   1   0   1
1   0   1   1   1   1   0   1
1   0   0   0   0   0   0   1
1   1   1   1   1   1   1   1

Time complexity of above solution is O(M*N).
Auxiliary space used by the program is O(1).

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding   🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
Justin
Guest
Justin

nice..

wpDiscuz