問題
幻想郷の一角。魔法の森。
そこには頭を悩ませる一人の魔法使いが居た。
彼女の名前はアリス。人形を操る魔法使いだ。
彼女は今、家のとある部屋の中にできるだけ大きな魔法陣を作ろうとしている。
魔法陣は縦と横 N * N マスの正方形である。
しかしその部屋には多くの人形がスタックされており、考えるのに苦悩している。
魔法陣は、人形のない床にのみ作ることができる。
人形は移動させることが出来る。
さて、彼女の部屋の俯瞰図が与えられるので、
作れる魔法陣の最大の面積を出力せよ。
入力
一行目に、部屋の縦の広さと横の広さ h , w が与えられる。
次の行から、h行に渡り、部屋の状態が与えられる。
# のとき人形、. の時何もないことを示す。
h w m1,1 m1,2 ... m1,w m2,1 m2,2 ... m2,w .. .. mh,1 mh,2 ... mh,w
出力
作成できる魔法陣の最大の面積を出力せよ。制約
- 1 ≦ H,W ≦ 2000
入出力例
入力例壱
3 4 ##.# #.#. #...
出力例壱
4
(2,3)の人形を(1,3)に移動させることで、
一辺が２、面積４の魔法陣を作ることが出来る。
入力例弐
4 6 .##.#. ##..## ...#.. .#..##
出力例弐
9