Problem F
Fair and Square
Felix has ordered a large rectangular pizza for his birthday party. He only quickly went to the kitchen to grab some plates and cutlery, and when he came back his guests had already started helping themselves to various parts of the pizza. The pizza, which originally was made up of $h\times w$ square pieces of equal size, is now missing some of these pieces:
![\includegraphics[width=0.62\textwidth ]{pizza.pdf}](/problems/fairandsquare/file/statement/en/img-0001.png)
To ensure that the distribution of the rest of the pizza proceeds in a much more orderly fashion, Felix wants to divide up the remaining pizza into larger square shaped areas. Felix can only cut along the grid lines and cannot rearrange any parts of the pizza. Each square should have the same side length, which should be as large as possible in order to minimize the number of plates needed.
Find this largest possible side length. Note that an answer always exists because the pizza can always be divided into $1\times 1$ squares.
Input
The input consists of:
-
One line with two integers $h$ and $w$ ($1 \le h,w \le 2500$), the height and width of the grid.
-
$h$ lines, each with a string of length $w$ consisting of ‘#’ (denoting pizza pieces that are still there) and ‘.’ (denoting pizza pieces that have already been taken).
It is guaranteed that the input contains at least one ‘#’.
Output
Output an integer, the largest possible side length such that the remaining pizza can be divided into squares of that side length.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 7 ####... ####.## .###### .####.. |
2 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 5 ##### ##### ###.. |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 5 .##.. ##### ##.## |
1 |
| Sample Input 4 | Sample Output 4 |
|---|---|
5 13 ....###...... ....###..###. .######..###. .###.....###. .###......... |
3 |
