NézetNyomtat

Legnagyobb üres téglalap
Címkék > Feladat

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