分数: 600 点
问题陈述
有一块板 N 行和 M 列。 该板的信息表示为 N 字符串 S_1,S_2,\ldots,S_N。 具体来说,正方形的状态为 i从顶部开始的第行和 j左起第 列表示如下:
- S_{i,j}=
.:方块是空的。 - S_{i,j}=
#:广场上放置了一个障碍物。 - S_{i,j}=
o:将一块棋子放置在正方形上。
Yosupo 重复以下操作:
- 选择一个棋子并将其移动到其右侧相邻的方格或其下方相邻的方格。 禁止将棋子移动到与另一棋子或障碍物一起的格子上。 将棋子移出棋盘也是禁止的。
Yosupo 希望尽可能多次地执行该操作。 找出最大可能的操作数。
约束
- 1 \leq N \leq 50
- 1 \leq M \leq 50
- S_i 是一个长度为的字符串 M 组成
.,#和o. - 1 \leq ( 件数 )\leq 100。
换句话说,对的数量 (i, j) 满足 S_{i,j}=
o介于 1 和 100,包括两者。
输入
输入由标准输入按以下格式给出:
N M S_1 S_2 \vdots S_N
输出
打印一行中可能的最大操作数。
示例输入 1
3 3 o.. ... o.#
示例输出 1
4
Yosupo 可以执行操作 4 次如下:
o.. .o. ..o ... ... ... -> ... -> ... -> ..o -> ..o o.# o.# o.# o.# .o#
示例输入 2
9 10 .#....o#.. .#..#..##o .....#o.## .###.#o..o #.#...##.# ..#..#.### #o.....#.. ....###..o o.......o#
示例输出 2
24