题目描述

新冠病毒具有很强的传染性且传染速度极快，如果未接种新冠疫苗的人接触到新冠患者，很容易被传染；如果已接种新冠疫苗的人接触到新冠患者，不容易被传染。

在一次会议中，所有参会人员座位排列为一个 M*M 的矩阵。因为来参加会议的人员有部分为新冠患者（自己不知情），在开会过程中又传染到周边相邻未接种疫苗的人员。新冠患者每隔一分钟就会传染到相邻未接种新冠疫苗的人员，被新传染后的新冠患者一分钟后还会继续传染与其相邻未接种新冠疫苗的人员，依此类推，但不会传染到已接种新冠疫苗的人员。（相邻是指上下左右相邻，斜对角不算相邻）

编写程序计算出N分钟后共有多少人为新冠患者？

例如：

N 为 3，M 为 4，4*4矩阵：

矩阵中 “P” 代表未接种新冠疫苗人员、“O” 代表已接种新冠疫苗人员、“X” 代表新冠患者（红色 “X” 表示新感染的新冠患者）。

初始时有 2 个新冠患者（如图一，红色 "X" ）；

1 分钟后 2 个初始新冠患者传染给其相邻的 4 个未接种疫苗人员（如图二，红色"X"）； 2 分钟后新传染的 4 个新冠患者传染给其相邻的 3 个未接种疫苗人员（如图三，红色"X"）； 3 分钟后新传染的 3 个新冠患者传染给其相邻的 1 个未接种疫苗人员（如图四，红色"X"）。 故 3 分钟后共有 10 人为新冠患者。

输入格式

第一行输入两个正整数 N（ 2 ≤ N ≤ 50 ），M( 2 ≤ M ≤ 100 )，分别表示分钟数及矩阵大小

从第二行开始输入 M 行，每行 M 个标识符（标识符 “P” 代表未接种新冠疫苗人员、“O” 代表已接种新冠疫苗人员、“X” 代表初始新冠患者，初始至少有一个 “X” ）

输出格式

输出一个整数表示N分钟后共有多少人为新冠病患者 （含初始新冠患者）

样例

3 4
PPPP
POPX
POXP
OPPP

10

2021 年 11 月 27 日 STEMA