← 返回题目列表

AtCoder · acl1_c

C. 移动件

中文机器翻译题面 查看原题

分数: 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