djb 的防御工事

题目描述

djb 最近在玩一个建造类沙盒游戏，这个游戏的地图可以看做一个 $n * m$ 大小的网格布局

这个游戏中存在村民和怪物两种角色，分布在整个地图中，用 V 表示村民，用 M 表示怪物

每个角色在每一回合都会沿着地图的上下左右四个方向随机的移动，一旦怪物能够碰到村民，djb 的游戏就会失败

现在 djb 作为建造者，他可以花费一定的材料在每个单位网格的边界上建造围墙

现在游戏还没有开始，djb 希望知道自己最少需要建造多少个围墙，才可以使得游戏不会失败？

输入格式

输入第一行包含两个整数 $n,m$ 表示地图大小 接下来 $n$ 行，每行一个长度为 $m$ 的字符串表示地图上角色分布情况 其中 V 表示村民，M 表示怪物，E 表示空地

输出格式

输出一个整数，表示 djb 最少需要建造的围墙数量

数据范围

对于 $10\%$ 的数据：$1\leq n,m \leq 3$。

对于 $30\%$ 的数据：$1\leq n,m \leq 20$。

对于 $100\%$ 的数据：$1\leq n,m \leq 100$。

样例输入

3 3
VVE
EEM
MMV

样例输出

5

样例解释

将左上角的 $V$ 封起来需要造 $3$ 个围墙，将右下角的 $V$ 封起来需要 $2$ 个围墙，共 $5$ 个