/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 600 点
問題文
H 行 W 列のグリッドがあります。各マスには +, -, # のいずれか一文字が書かれています。上から i 行目、左から j 列目のマスを (i,j) と表します。グリッドの情報は H 個の長さ W の文字列 S_1, S_2 , \dots ,S_H によって与えられ、S_i の j 文字目が (i,j) に書かれています。
あなたは、次の操作を 0 回以上行うことができます。
#でないマスを 1 つ選ぶ。「選んだマスから#のマスを通ることなく、隣接するマスへ左・右・下のいずれかの方向に移動することだけで到達できるマス」をすべて#に変える。ただし、選んだマス自身も到達できるマスに含まれる。
操作後のグリッドにおける、+ のマスの個数から - のマスの個数を引いた値としてあり得る最大値を求めてください。
制約
- 1 \le H,W \le 30
- S_i は
+,-,#からなる長さ W の文字列 - H, W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 S_2 \vdots S_H
出力
答えを出力せよ。
入力例 1
2 3 +-+ --+
出力例 1
1
(2,1) を選ぶと、2 行目の全てのマスが # に変わります（上方向には移動できないことに注意してください）。残る 1 行目には + が 2 個、- が 1 個あるため、値は 2-1=1 で、これが最大です。
入力例 2
3 3 +-- -#- #+#
出力例 2
1
(1,1) を選ぶと、(3, 2) を除いて # になります。マス (1, 1) 自身も到達できるマスに含まれることや、 # のマスは通れないことに注意してください。
入力例 3
5 7 ++#--++ -+---+# ##++-++ --#-++- +---#++
出力例 3
5
Score : 600 points
Problem Statement
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).
You can perform the following operation zero or more times:
- 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.
Constraints
- 1 \le H,W \le 30
- S_i is a string of length W consisting of
+,-,#. - H and W are integers.
Input
The input is given from Standard Input in the following format:
H W S_1 S_2 \vdots S_H
Output
Output the answer.
Sample Input 1
2 3 +-+ --+
Sample Output 1
1
If you choose (2,1), all cells in row 2 change to # (note that you cannot move upward). The remaining row 1 has two cells of + and one cell of -, so the value is 2-1=1, and this is the maximum.
Sample Input 2
3 3 +-- -#- #+#
Sample Output 2
1
If you choose (1,1), all cells except (3, 2) become #. Note that the chosen cell (1, 1) itself is included among the reachable cells, and that you cannot pass through a cell that is #.
Sample Input 3
5 7 ++#--++ -+---+# ##++-++ --#-++- +---#++
Sample Output 3
5