开始: 2025-06-27 00:00:00

2025.6.27新生摸底测试赛

结束: 2025-06-30 00:00:00
当前  2025-07-18 10:59:02  类型: IOI  状态: 已经结束 

P3. 三子棋
描述

33DAI 很喜欢三子棋。今天他在一张很大的方形棋盘上下棋,棋盘可以看作是一个 nm 列的网格。(大家应该知道三子棋是下在格子里面的吧?)

33DAI 今天的玩法非常不一样。棋盘上有些位置上有棋子,有些位置上没有。所有的棋子都是己方棋子。33DAI 可以任选一个空着的位置下棋。如果他落子的位置能和周边的另外两个棋子构成三连(横着、竖着、斜着都可以),那么这就是一个好位置。

请你帮 33DAI 找找棋盘上有多少个好位置吧!


输入

第一行为空格隔开的两整数 nm。  

接下来 n 行,每行为 m 个字符,描述了整个棋盘,第 i 行第 j 列的字符为 g_{i,j},描述了第 i 行第 j 列的格子。

如果字符为 . 则表示这个位置没有棋子,如果字符为 # 则表示这个位置有一个己方棋子。


输出

一行一个整数,表示有多少个空着的位置是好位置。

样例

输入

5 7
.......
...#...
...##..
.......
...#..#

输出

6
提示

样例解释

下面用字符 o 标出了所有好位置

..oo...
...#...
..o##o.
...o.o.
...#..#

数据规模与约定

对于 100\% 的数据,1\le n, m\le 50g_{i,j}.# 中的一种。

  • 子任务 1(30 分):保证有且仅有两个位置为 #

  • 子任务 2(30 分):保证每个 # 与其他 # 的行数要么相同,要么相差大于 2。即不会产生竖着、斜着的三连。

  • 子任务 3(40 分):无特殊限制


提交

题目参数
时间限制 1 秒
内存限制 128 MB
提交