Java - Ejercicio Complicado Construyendo una Casa (ayuda desde 0)

Estimados después de un día completo investigando. no se me ocurre ninguna forma de desarrollar este ejercicio pero quiero aprender a desarrollarlo. me gustaría una ayuda paso a paso se agradecería en montón o alguna pista. Saludos.

Construyendo una casa

Problema:
Usted a comprado un terreno y quiere construir una casa rectangular lo más grande
posible, pero su terreno posee un serie de obstáculos. Su terreno está divido en
cuadrados que contienen hierba (H), roca (R), agua (A), matorrales (M) y árboles (T).
Mientras la hierba y los matorrales se pueden cortados y sacados del suelo, las rocas,
el agua y los árboles no pueden ser extraídos. Dados estos obstáculos, determine el
área rectangular más grande posible para construir la casa.
Entradas:

La primera línea debe ser el número de casos, N.
Por cada caso debe haber:
- Una línea que contenga dos números enteros separados por un espacio que indican
el Largo (L) y ancho (W) del terreno.
- Seguido por W filas, cada una contiene L caracteres donde cada uno indica las
condiciones de cada cuadrado que compone el terreno.
Limites:
1 <= L <= 50
1 <= W <= 50
Ejemplo:
- Entrada (archivo de entrada)
4
1 1
H
2 2
HM
MH
2 2
HT
HH
5 8
HHTHH
THHHH
HMMHT
HHHHT
HAHHH
RHTRT
RTHAT
ATAHR

- Salida
Caso 1: 1
Caso 2: 4
Caso 3: 2
Caso 4: 9