题目描述

有一个纵向 $H$ 行、横向 $W$ 列的网格。从上往下第 $i$ 行、从左往右第 $j$ 列的格子的状态由字符 $a_{ij}$ 表示，具体如下：

• . ：表示空格子。
• o ：表示有一个机器人放置在该格子上。
• E ：表示有出口的格子。整个网格中恰好有一个 E。

高桥君可以进行若干次如下操作，尽可能多地救出机器人：

• 选择上下左右中的一个方向，将所有机器人向该方向移动一格。此时，移动到出口格子的机器人会立即被救出并从网格中消失。移动到网格外的机器人会立即爆炸并从网格中消失。

请你求出高桥君最多能救出多少个机器人。

输入格式

输入以以下格式从标准输入读入。

$H$ $W$
$a_{11} a_{12} \ldots a_{1W}$
$a_{21} a_{22} \ldots a_{2W}$
$\vdots$
$a_{H1} a_{H2} \ldots a_{HW}$

输出格式

输出高桥君最多能救出的机器人数。

样例 1

输入

3 3
o.o
.Eo
ooo

输出

3

样例 2

输入

2 2
E.
..

输出

0

样例 3

输入

3 4
o...
o...
oooE

输出

5

样例 4

输入

5 11
ooo.ooo.ooo
o.o.o...o..
ooo.oE..o..
o.o.o.o.o..
o.o.ooo.ooo

输出

12

说明/提示

限制条件

• $2 \leq H, W \leq 100$
• $a_{ij}$ 只会是 .、o 或 E。
• 整个网格中恰好有一个 E。

样例解释 1

例如，可以依次向左、上、右移动机器人。

样例解释 3

可以依次向右、右、右、下、下移动机器人。

由 ChatGPT 4.1 翻译