COCI 2008/2009, Contest #1
Archeologists recently found the remains of Greco-Roman architecture. The location can be modeled as a grid of R·C square cells. For each of the cells, archeologists have determined if some building was there or if the cell has always been empty.
After examining the artifacts in detail, they concluded that the location contains two buildings from different periods in time, and that the floor plans of both buildings are of square shape.
Because the buildings were from different periods in time, it is possible that their floor plans overlap. Determine the possible location and size (length of the side of the square occupied by the floor plan) for each building.
InputThe first line contains two integers R (1 ≤ R ≤ 100) and C (1 ≤ C ≤ 100), the size of the location.
Each of the next R lines contains a string of C characters '.' (dot) or 'x' (lowercase letter).
The character '.' means that nothing was found in that cell, while 'x' indicates that there was a building there.
OutputFor each of the two buildings, output on a single line the row and column of its upper left corner, and the size of the building.
Note: The test data will guarantee that a solution always exists, although it may not necessarily be unique.
3 3 xx. xxx ...
1 1 2 2 3 1
4 6 xx.... xx.xxx ...xxx ...xxx
1 1 2 2 4 3
5 5 ..... xxx.. xxxx. xxxx. .xxx.
2 1 3 3 2 3
Point Value: 15
Time Limit: 1.00s
Memory Limit: 32M
Added: Oct 18, 2008
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3