Jake was having a nice dinner with his girlfriend in one of their favorite restaurants. She was talking about feelings or something, and as it was often the case, Jake’s mind started wandering.
The wall behind her caught his attention. It was one of those old looking walls composed of tiles with different sizes and shapes. The wall was huge and he started thinking about the ammount of work that was put into building such a structure.
As he slipped deeper and deeper into his own imagination, he suddenly realized that the wall was a sham. He could see it clearly now. The wall was made out of much larger rectangular blocks, all with the same size and orientation, and each one of them was composed of several smaller tiles. The magic was gone!
"Were you listening to anything I said?", she asked. He nodded, as he tried to get the waiter’s attention, "Check please!". There was only one thing on his mind now: How many blocks was the wall really made of?
Task
Consider a wall that is apparently made of several small tiles. These tiles are not necessarily rectangles and can be imagined as a group of squares joined together at their edges.
A tile can only belong to one block. The wall is in fact made of larger rectangular blocks always having the same dimensions and orientation (but not necessarily the same tile patterns).
Near the wall edges, blocks can be cut into smaller pieces to fit the available space (but always maintaining the same orientation). Inner blocks, however, will always have the same size.
Given the configuration of a wall, as a grid, where a tile is defined as a collection of adjacent grid squares having the same capital letter, determine the smallest block that could be used to create the desired illusion.
Input
The first line of the input will contain two integers, W and H, representing the size of the wall. The next H lines will contain W characters from ’A’ to ’Z’ representing the wall’s configuration. If two consecutive characters (horizontally or vertically) on the grid are the same then they belong to the same tile.
Output
A line with two integers representing the width and height of the smallest block that could be used.
Constraints
1 ≤ W,H ≤ 1,200 width and height of the wall Input example 1
14 9 AABAABCEAAAEED CDEDBDDECCDACD ADEDAABECCBBCD BBEBBCCCAACCEE AAFFFFDDEBBABC BDEBFFBCACEFFC ADEDDDECACDDAC BBCAABBEABBEEE DDEBBCAACDDDAAOutput example 1
6 4Input example 2
11 11 ABBABBBAABD BCCBCCDEBAC BCABDDDEBAC ABBABABAABA BAABDDDBDAB BCACBBDBDAC BDABDDDBBAD ABCACACAACE ACCBAAABACA BAACDDDABAB ACCAEEEZZYXOutput example 2
3 3
MIUP'2012, 20 de Outubro, DCC/FCUP
This document was translated from LATEX by HEVEA.