级联网格AI (CI翻译)
Problem Statement
题目描述
AI (CI翻译)There is a grid with $H$ rows and $W$ columns. Each cell has one of the characters +, -, # written on it. Let $(i,j)$ denote the cell at the $i$-th row from the top and the $j$-th column from the left. The grid is given by $H$ length-$W$ strings $S_1, S_2 , \dots ,S_H$: the $j$-th character of $S_i$ is written on $(i,j)$.
有一个 $H$ 行 $W$ 列的网格。每个格子中写有字符 +、-、# 中的一个。记从上往下数第 $i$ 行、从左往右数第 $j$ 列的格子为 $(i,j)$。网格由 $H$ 个长度为 $W$ 的字符串 $S_1, S_2 , \dots ,S_H$ 给出：$S_i$ 的第 $j$ 个字符写在格子 $(i,j)$ 中。AI (CI翻译)
You can perform the following operation zero or more times:
你可以进行零次或多次以下操作：AI (CI翻译)
- Choose one cell that is not
#. Change to#all cells that are "reachable from the chosen cell only by moving to an adjacent cell in the left, right, or down direction without passing through a cell that is#." Here, the chosen cell itself is included among the reachable cells.
- 选择一个不是
#的格子。将所有“从所选格子出发，只向相邻的左、右或下方格子移动，且途中不经过#格子”可以到达的格子都变为#。其中，所选格子本身也算作可以到达的格子。
Find the maximum possible value of the following value in the grid after the operations: the number of + cells minus the number of - cells.
求进行操作后，网格中以下数值的最大可能值：+ 格子的数量减去 - 格子的数量。AI (CI翻译)
Constraints
约束条件
AI (CI翻译)$1 \le H,W \le 30$$S_i$is a string of length$W$consisting of+,-,#.$H$and$W$are integers.
$1 \le H,W \le 30$$S_i$是一个长度为$W$、仅由+、-、#组成的字符串。$H$和$W$均为整数。
Input
输入格式
AI (CI翻译)The input is given from Standard Input in the following format:
输入从标准输入按以下格式给出：AI (CI翻译)
H W
S_1
S_2
\vdots
S_HH W
S_1
S_2
\vdots
S_HOutput
输出格式
AI (CI翻译)Output the answer.
输出答案。AI (CI翻译)
样例
2 3
+-+
--+
1
3 3
+--
-#-
#+#
1
5 7
++#--++
-+---+#
##++-++
--#-++-
+---#++
5
题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。