seuOJ561 - 猫娘部署

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：2000 ms
• 空间限制：1024 MiB
• 题目标签：

题目描述

公元 2225 年，为满足广大同学的精神需求，车南大学资产管理处投资 5000 万元，拟将车南大学广寒宫校区的猫猫升级为猫娘。

车南大学广寒宫校区可以视为一个 $n$ 行 $m$ 列的二维网格，每个格子有两种状态：有猫（Y）和无猫（N）。

显然，猫娘必须在有猫地区部署；并且，由于猫娘需要更加良好的饲养环境，任意两只猫娘不能相邻。定义相邻为上下左右四个格子相邻。

同学们希望猫娘的数量尽可能多，请你计算出猫娘的最大数量。

输入格式

第一行两个整数 $n,m(1 \le n, m \le 8)$，表示网格大小。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示网格。

输出格式

输出一个整数，表示猫娘的最大数量。

样例

4 4
YYYY
YYNN
NYNY
YYYY

7

数据范围与提示

样例解释

在 $(1, 2), (1, 4), (2, 1), (3, 2), (3, 4), (4, 1), (4, 3)$ 位置部署猫娘可以最大部署 $7$ 只猫娘。