题目背景

艾莉被绑架并关在一座庞大的宅邸中。幸运的是，她找到了一张宅邸平面图；不幸的是，被带进来时她一直蒙着眼睛，因此不知道自己究竟位于哪一个房间。

宅邸里有畅通的走廊，也有需要花时间破坏的墙。艾莉会选择最优路线逃到建筑外，而她认为自己很可能正处在“最难逃出去”的位置。

请根据平面图，判断有多少个空地格可能是这种最坏位置。

题目描述

宅邸可以表示为一个 $N imes M$ 的网格。

每个格子是以下两种类型之一：

• .：空地，可以直接通过；
• #：墙壁，穿过之前必须将其破坏。

艾莉最初位于某个 . 格子中，但具体位置未知。

她每次可以向上、下、左、右移动到相邻格子，不能斜向移动。

• 移动到空地格不耗费时间；
• 移动到墙壁格时，需要先破坏该墙壁，耗时 $1$ 小时。

艾莉可以从任意边界格直接走出网格。也就是说，网格外部可以视为一片畅通区域：

• 若她到达一个边界空地格，可以立即离开；
• 若边界格是墙壁，则需要先破坏这面墙，之后才能离开。

对于每个空地格，定义它的逃脱时间为：从该格出发，在选择最优路线的情况下，逃到网格外部所需破坏的墙壁数量。

请找出逃脱时间最大的所有空地格，并输出这些格子的数量。

输入格式

第一行包含两个整数 $N,M$，分别表示网格的行数和列数。

接下来 $N$ 行，每行包含一个长度为 $M$ 的字符串，描述宅邸平面图。

字符串中的每个字符均为 . 或 #。

输出格式

输出一个整数，表示逃脱时间达到最大值的空地格数量。

数据范围

对于所有测试数据：

• $1\le N\le100$；
• $1\le M\le100$；
• 所有输入行长度均为 $M$；
• 每个字符均为 . 或 #；
• 网格中至少存在一个 . 格子。

样例 1

输入

7 14
.#............
.#####........
.#.#..#.......
.##.#.#.......
.#.#..#..####.
.#...##..#.##.
..####...###..

输出

1

解释

平面图中存在三层封闭区域，其中一个区域嵌套在另一个区域内部。最深处空地逃出时需要破坏最多的墙壁，满足条件的格子只有一个。

样例 2

输入

3 3
..#
...
.#.

输出

7

解释

部分位置无需破坏任何墙壁即可逃出。所有空地格的最短逃脱时间相同，因此它们都可能是艾莉所在的位置。

样例 3

输入

12 18
#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#

输出

8

解释

艾莉只能上下左右移动，不能沿对角线穿过相邻空地。

样例 4

输入

11 9
#########
#########
#########
#########
####.####
####.####
####.####
#########
#########
#########
#########

输出

3

解释

三个空地格都被多层墙壁保护，它们的最优逃脱时间相同且达到最大值。

样例 5

输入

50 50
#...##.......#..#..#..#.#..#..###............##...
....#.....#....#...###..#....#......#.#.......#.#.
......#....#..#.....#.#..#...#.#..##.......#.....#
................#..#......##........#..#....##...#
###..#..#.#....##...#...........#.##..###..##.....
.##..#......#...........#.##...##..#.....#.....#..
....#..##...#..#.#........##.#....................
.#.#.#.##.....#.........#......#.......#..#.##.#..
..#....#......#........#...#.#...#.#....#........#
#.#....#..#.#.#.#....#.....................#.#....
.#....#..#.......#.........#....#.#............##.
..##......#....###..#...#.#..#.....##........#..#.
........#.#..........#......#........##.#.#.#....#
....#.#..####...#..#.....#.###..##....#.#.......#.
....#....#...#................###.#......##.......
.#.....#..#.....##....#......................##.#.
#.................#.......#...#...........#....#..
............#........#.....#.#.....#.#.....#..##..
#......#.#..#.#.##..#.........#..#.#.....#.....#..
....#..###.#........#.#.....................##....
......##...###..#...#.##..#..#.##....#.........##.
.......#...............#....#...#......##....#..#.
.#...#.##....#...#........###..##.#....#...##.....
....#........#..............#..###.#.#..#.....#.##
.#...#..#.....#.#...#...........#....##.....#.#...
...#..#.#.#..##....#............#.....#........###
.##......#.#..##.......###...##...................
..........#.............#.#...#.....###...##..##..
.......##...#.#...#.........#.#.....#.#..#.#...#..
####.........#.#.....#....#.#......#.#.....#..#...
.#.#...#..###...#.#.#.....###.#....##.....#...#..#
.#..#.##.#.###....#.###..#..........#...#.........
##..#.#....#..##...#.....##..#..##..............##
#.##.##..........##.#....##......#...#.....##...#.
.....#........#..............#.....####.######....
..##............#..###.##...#.#...#.....#.#...#..#
...##..#.#...#......#.#..........#..#..##..#.#..#.
..##.####......#....#....#.....#......#....##.....
#.......####.#......##.#.....#..#........#...##.#.
..#.....#..###....#......#..#........#....####....
......#.....#..................#.........#.##...#.
...#....#....##......#.#.....#.....#....#......#..
....#.##...#.#....#..#.#...#.......##.......#.#...
...#..#.#.##.#.....###....#.###.....##.#......#...
.#.#......#.....#.....#...........##...#.....#.##.
..........#.....#...#.##....#..........#.....###..
........##..#.....#...#....##..#......##.......#..
.....#....##....#.....#....#.#.#.........#........
..#...##......#.#............#....#.##...#....#...
..##...#.#...#......#....##.#.#..#......#..######.

输出

13