Description
While scouting outside the wall, the Survey Corps spotted a wide open field filled with a lot of titans. In order to maneuver around the titans, commander Hange recommends using a quadtree structure to scan the area. When viewing the field, it can be divided into a matrix where each block represents whether an area has any titans. Each block can either contain a 0 or a 1. If the given number is 0, then there are no titans in the block. If the given number is 1, then there are titans in the block. An example can be given below:
To use the quadtree structure, we must first divide the initial area to 4 separate quadrants (upper left, upper right, lower left, lower right). In the example, the upper left quadrant is completely homogenous (all areas inside have the value of 0 or 1) while the other quadrants are not; therefore the upper left quadrant can be ignored while the others must be divided further. Non-homogenous quadrants will then be divided further until it each area in the quadrant is homogenous.
Alongside this structure, Hange also applied a specific naming procedure for each homogenous area:
- The first digit of an area's ID will be the homogenous value within the quadrant.
- Every following digit represents the location of the current block corresponding to the previous ones. (e.g. if the current block is the upper left quadrant of the previous block then the next digit will be 0.)
Following these rules the result of the given example would look as follows:
One more thing to note is that because of the nature of the quadtree, the length and width of the area must be equal and have the value of 2P. If is does not follow this condition, the area must be padded with 0's so it fits the dimensions accordingly. (e.g. 3 * 5 area must be rounded to a 8 * 8 area).
Create a code to perform Hange's quadtree structure with the aforementioned conditions to find the areas that contains titans.
P.S.
Input
The first line contains the integer R and C (1 <= R,C <= 128).
The following R lines contain C values of the matrix to be processed.
Output
The first line contains the number (N) of homogenous areas with the value of 1.
The following N lines contain the ID of each area with the homogenous value of 1.
Don't forget to put a newline character at the end.