← 返回题目
题库练习 Cascading Grid
← 上一题 下一题 →

A7724 | Cascading Grid

时间限制2s
内存限制1024MB
通过 / 提交0/0

题目描述

有一个 $H$ 行 $W$ 列的网格。每个格子中写有字符 +、- 或 # 中的一个。记 $(i,j)$ 为从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子。该网格由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2 , \dots ,S_H$ 给出：$S_i$ 的第 $j$ 个字符即为格子 $(i,j)$ 上所写的字符。

你可以执行以下操作零次或多次：

* 选择一个**不是 #** 的格子。将所有“仅通过向左、向右或向下移动（不能经过 # 格子）即可从所选格子到达”的格子全部变为 #。注意：所选格子自身也属于可达格子。

求经过若干次操作后，网格中（+ 的个数减去 - 的个数）的最大可能值。

输入格式

输入从标准输入中按以下格式给出：

> $H$ $W$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$

输出格式

输出答案。

输入输出样例

输入 #1
2 3
+-+
--+
输出 #1
1
输入 #2
3 3
+--
-#-
#+#
输出 #2
1
输入 #3
5 7
++#--++
-+---+#
##++-++
--#-++-
+---#++
输出 #3
5
C++ 编辑器
输入
输出