A7724. Cascading Grid
编程题
入门
知识点
题目描述
有一个 $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$
> $H$ $W$
> $S_1$
> $S_2$
> $\vdots$
> $S_H$
输出格式
输出答案。
输入输出样例
输入 #1
2 3 +-+ --+
输出 #1
1
输入 #2
3 3 +-- -#- #+#
输出 #2
1
输入 #3
5 7 ++#--++ -+---+# ##++-++ --#-++- +---#++
输出 #3
5
说明/提示
**样例 1 解释：**
若选择位置 $(2,1)$，则第 $2$ 行的所有格子均变为
**样例 2 解释：**
若选择位置 $(1,1)$，则除 $(3, 2)$ 外的所有格子均变为
### 限制条件
* $1 \le H,W \le 30$
* $S_i$ 是一个长度为 $W$ 的字符串，仅由字符
* $H$ 和 $W$ 均为整数。
若选择位置 $(2,1)$，则第 $2$ 行的所有格子均变为
#（注意：你不能向上移动）。剩余的第 $1$ 行包含两个 + 和一个 -，因此得分为 $2-1=1$，这是最大可能值。**样例 2 解释：**
若选择位置 $(1,1)$，则除 $(3, 2)$ 外的所有格子均变为
#。注意：所选格子 $(1,1)$ 本身属于可达格子之一，且你无法穿过标记为 # 的格子。### 限制条件
* $1 \le H,W \le 30$
* $S_i$ 是一个长度为 $W$ 的字符串，仅由字符
+、-、# 组成。* $H$ 和 $W$ 均为整数。