Legnagyobb üres téglalap
Adott egy téglalap alakú telek térképe. Szeretnénk a legnagyobb alapterületű házat építeni a telekre. A térkép egységnégyzetekre van felbontva, minden ilyen cella értéke a következők valamelyike lehet:
- fű - grass (G)
- szikla - rock (R)
- víz - water (W)
- bokrok - shrubs (S)
- fák - trees (T)
Alapozásnál a fű lenyírható, a bokrok kivághatók, de sziklára és vízre nem építhetünk, a fákat pedig nem szabad kivágni.
Feladat
Adjuk meg a legnagyobb lehetséges alapterület értékét!
Bemenet
Az első sor a tesztesetek számát adja meg. Ezután minden tesztesethez leírjuk a
telek méreteit (1<= A, B <= 50), majd B sorban A darab karakter következik, a térkép
cellái.
Kimenet
Minden tesztesethez a legnagyobb lehetséges alapterületet kell megadni.
Példa
|
Input
|
Output
|
4
1 1
G
2 2
GS
SG
2 2
GT
GG
5 8
GGTGG
TGGGG
GSSGT
GGGGT
GWGGG
RGTRT
RTGWT
WTWGR
|
Case #1: 1
Case #2: 4
Case #3: 2
Case #4: 9
|
Tesztadatok
