The Game of Rocks

Labib666 The Tough Summer Spar 201...
Limits 500ms, 512 MB

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.


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.)


Login to submit.


77% Solution Ratio
nfssdqEarliest, Jul '16
Kuddus.6068Fastest, 0.0s
bqi343Lightest, 393 kB
bqi343Shortest, 1762B
Toph uses cookies. By continuing you agree to our Cookie Policy.