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 |