Rectangle màxim P67108

Donat un tauler n × m amb caselles lliures i ocupades, trobeu-hi el rectangle lliure d’àrea màxima. Aquest rectangle ha d’estar alineat amb els eixos horitzontal i vertical.

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguides d’n files amb m caràcters cadascuna. Un punt indica una posició lliure, i una ‘X’ una posició ocupada. Suposeu que n i m estan entre 1 i 1000.

Sortida

Per a cada cas, escriviu la màxima àrea possible.

Observació

Podeu obtenir 25 punts resolent casos on n i m no superen 10, i un total de 70 punts resolent casos on n i m no superen 30.