米尔科买了一套别墅,他想要邀请尽量多的人和他一起庆祝。
他需要一张大的木质矩形桌子来让他和他的嘉宾坐下。每张桌子可容纳的人数等于它的周长(四边长度的总和)。米尔科想要买一张即可在他的公寓里放下,也可以坐下尽量多的人和他一起享用晚餐的桌子。桌子必须放置成四条边都与公寓的墙平行的样子。
题目给出公寓内部的布局,请问米尔科最多可以邀请多少人吃晚餐(不算米尔科自己)。
第一行包含两个整数 R 和 S,代表公寓的尺寸(R 为宽,S 为长),以下的 R 行中每一行都包含了 S 个的字符(没有空格),代表这个正方形区域是没有障碍的(.
),还是有障碍的(X
),米尔科只会把桌子放在没有障碍的正方形区域里。
输出为一个数,即米尔科最多可以邀请多少人吃晚餐。
2 2 .. ..
7
4 4 X.XX X..X ..X. ..XX
9
3 3 X.X .X. X.X
3
选择左上角为 (3,1),右下角为 (4,2) 的矩形摆放桌子,周长为 (2+2)\times 2=8,可以邀请 8-1=7 个客人。
对于 100\% 的数据,1\le R,S\le400。