IN C$++$

Write a program that finds the minimal number of groupings in a matrix of bits. The size of a

grouping is determined by the number of $1\text{'}$s in it$.$ The rules in forming groups of ones are as follows:

$$ Each group should contain the largest number of 'ones' and no blank cells.

$$ The number of 'ones' in a group must be a power of $2.$ A group can contain:

$$ Grouping is carried$-$on in decreasing order meaning, one must try to group for $8($octet$)$ first,

then for $4($quad$),$ followed by $2$ and lastly for $1($isolated 'ones'$).$

COSC $2436$ S$24$

$5$

$$ Grouping is done either horizontally or vertically or in terms of rectangles$/$squares$.$ Diagonal

grouping of 'ones' is not permitted.

$$ The same element$($s$)$ may repeat in multiple groups only if this increases the size of the group.

$$ The elements around the edges of the matrix, including the four corners, are adjacent and can

be grouped together.

In review:

$$ No zeros allowed.

$$ No diagonals.

$$ Only power of $2$ number of cells in each group.

$$ Groups should be as large as possible.

$$ Every $1$ must be in at least one group.

$$ Overlapping and wrapping around allowed.

$$ Get the fewest number of groups possible.

Input from the keyboard the size of the rows and columns in the range $[2,5].$ Error check. The program

will randomly fill the matrix with the numbers $0$ or $1.$ Output to the screen the matrix along with the

minimum number of rectangles covering the $1$ values based on the rules above. Finally, the program

should ask if the user wants to run the program again $($Check case$).$ Refer to the sample output below.

Sample Run:

Enter rows $[2-5]$: $2$

Enter cols $[2-5]$: $4$

COSC $2436$ S$24$

$6$

Generated grid:

$1001$

$1000$

Min number of rectangles$/$squares formed: $2$

Run Again $($Y$/$N$)$: y

Enter rows $[2-5]$: $2$

Enter cols $[2-5]$: $4$

Generated grid:

$1001$

$1001$

Min number of rectangles$/$squares formed: $1$

Run Again $($Y$/$N$)$: Y

Enter rows $[2-5]$: $4$

Enter cols $[2-5]$: $4$

Generated grid:

$1010$

$0100$

$0000$

$0001$

Min number of rectangles$/$squares formed: $4$

Run Again $($Y$/$N$)$: y

Enter rows $[2-5]$: $4$

Enter cols $[2-5]$: $4$

Generated grid:

$1101$

$0000$

$0000$

$1001$

Min number of rectangles$/$squares formed: $2$

Run Again $($Y$/$N$)$: Y

Enter rows $[2-5]$: $4$

Enter cols $[2-5]$: $4$

COSC $2436$ S$24$

$7$

Generated grid:

$0001$

$0001$

$0011$

$1111$

Min number of rectangles$/$squares formed: $3$

Run Again $($Y$/$N$)$: y

Enter rows $[2-5]$: $3$

Enter cols $[2-5]$: $5$

Generated grid:

$00010$

$11110$

$11110$

Min number of rectangles$/$squares formed: $2$

Run Again $($Y$/$N$)$: N