题目背景

小王的最近痴迷于玩游戏，但是他太菜了，想找你帮忙解决问题嘿嘿嘿

请用BFS求解。

题目描述

晓莉同学特别喜欢滑冰，在家长的鼓励下，参加了一个"绕障碍"的滑冰活动。

这个滑冰的场地是一个 $N \times M$ 网格。为了方便表示，令 $(i,j)$ 表示这个网格从上往下第 $i$ 行，从左往右第 $j$ 列的方格。

这个网格的每个方格都是冰或障碍，用长度为 $M$ 的 $N$ 个字符串 $S_1,S_2,\dots,S_N$ 表示，如下所示：

• 如果 $S_{ij}$ 是"."，则 $(i,j)$ 号方格是冰；
• 如果 $S_{ij}$是 #，则 $(i,j)$ 号方格是障碍。

这个网格的最外围一圈（ 第一行、第$N$行，第一列、第$M$列中的所有方格）是障碍物。

在游戏开始前，晓莉停留在 $(2,2)$ 这个方格上，保证这个方格是冰。

晓莉可以走下面的步骤零次或无限多次：

• （一）指定移动方向：向上、向下、向左或向右。
• （二）一直朝指定的这个方向移动，直到玩家撞到一块障碍后停止。即：
  • 如果移动方向的下一个方格是冰，则走到该方格并继续移动；
  • 如果移动方向的下一个方格是岩石，则停留在当前方格并停止移动，回到（一）。

请找出晓莉最多可以触碰（通过或停留）的冰方格数。一个方格只能被计算$1$次。

输入格式

第一行输入两个数字$N$ $，M$，分别代表 这个地图的行数和列数。

第二行开始，共$N$行，每行有一个长度为 $M$ 的字符串$S_i$，由 # 和 .组成，分别代表障碍和冰。

输出格式

请输出晓莉最多可以触碰（通过或停留）的冰方格数。

样例

6 6
######
#....#
#.#..#
#..#.#
#....#
######

12

3 3
###
#.#
###

1

样例解释

对于第一个样例，晓莉可以有如下的运动路径：

可以进行(2,2)→(2,5)→(5,5)然后进行其他移动，但是不能(2,2)→(2,4)→(3,4)，因为(2,4)没有前进到障碍物，不能更改前进方向。

请注意，相同的网格只能计算一次，即多次路过同一个位置只能计算一次冰方格。

可以证明，针对本样例，没有方案能使方格数大于12。

数据范围

对于$20\%$的数据， $3\le N,M \le 30$。

对于$40\%$的数据， $3 \le N,M \le 100$。

对于$100\%$的数据， $3 \le N,M \le 200$。

保证方格 $(2,2)$ 是冰。