The Game of Rocks
Alice and Bob have come up with a new game.
Bob gives Alice a NxM grid that contains N rows and M columns. Each cell of this grid is either empty or it contains a rock. To win this game, Alice has to choose a rectangle with the highest perimeter enclosed by rocks. The sides of this rectangle has to be axis parallel. The rectangle has to enclose a positive area. If there are multiple such rectangles, Alice has to choose one with the maximum area enclosed by the rocks (See the sample I/O for more detail).
Can you help Alice win this game?
First line of the input contains an integer: T, the number of test cases.
First line of each test case contains two integers: N and M.
The next N lines describe the grid Bob provides. Each line contains M characters. Each character is a *(asterisk) or a .(dot) , where *(asterisk) represents a rock and .(dot) represents an empty cell.
1 <= T <= 10
1 <= N, M <= 200
For each case, print two space separated integers on a separate line: the maximum perimeter and the maximum area enclosed by such a rectangle.
If no rectangle can be formed that encloses a positive area, you must output “No solution” without the quotes.
4 3 3 *** *.* *** 2 3 *** *** 3 3 *.* *.* *** 6 8 *.....** ***...** ******** *.*.*.** *.*.**** ***.****
8 1 No solution No solution 12 4
In the first case, there is only one valid rectangle which has length = width = 3. Thus, perimeter = 2(3+3)-4 = 8. It bounds an area of size 1.
In the second case, there is no rectangle that encloses a positive area. Thus there is no solution.
In the third case, there is no valid rectangle. A rectangle must be enclosed by rocks only. Thus there is no solution.
In the fourth case, there are two candidate valid rectangles that we can choose from (enclosed by rocks, enclose a positive area and have the maximum possible perimeter). The maximum area enclosed by these rectangles is 4 (Notice that it does not matter if there is any rock inside the rectangle or not.)
Labib666Labib loves to solve problems unless confronted with real life ones which he procrastinates upon with food and sitcoms. →