CWB - Chipmunks with Brain

no tags 

There is a Chipmunk with "Brain" and he want to dig holes in a yard to store his food.
There is a rectangular yard which is divided into unit cells, initially having some holes(H) and sand(S). The chipmunk can dig one row at a time, But he have to dig all the sand(S) positions simultaneously and due to this holes(H) which are already there got filled with sand.

Example:
Suppose a Row is "SHSHH" then after digging the row becomes "HSHSS" i.e. all "S" replace with "H" and vice versa.

Now Chipmunk wants to have a large square of holes somewhere in the yard. The sides of square must be parallel to the sides of the yard. Find a sequence of turns that produces the largest possible square of holes somewhere in the yard and help him to find the area of that square.

Input

Given two integer Rows(R) and column(C) (1<=R,C<=30)
Next line contain a RxC rectangular yard of sand (S) and hole (H).

Output

Print largest "Area of the Square" that can be obtain after sequence of turns.

Example

Input:
2 2
SS
HH
Output: 4
Input:
5 1
H
S
H
H
H
Output: 1

hide comments
lumaks_69: 2022-03-21 22:10:35

O(R*C) @psz2007

Last edit: 2022-03-21 22:10:59
psz2007: 2021-10-09 06:58:39

What is the best time complexity of the problem?

I write a program with O(n^3logn)(worst) and passed.

:D: 2016-10-21 22:39:35

Just to clarify, you can only change rows. That is, columns can't be processed in any way.

J_P: 2014-08-30 19:09:41

nice one.. :)

BLANKRK: 2014-06-25 17:35:49

done!! :)

Mitch Schwartz: 2014-06-19 01:04:17

The optimisation possibilities for this problem are kind of interesting. It could be nice to have a version with higher constraints and multiple cases per input file for proper speed comparison. (And uniform random input wouldn't be sufficient, it would require a little thought.)

shiv prasad chabarval: 2014-06-10 20:00:59

@Quantum : what do u mean by one row at a time ?


Added by:P_Quantum
Date:2014-04-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All