E - 変な足し算
Editorial
/
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
縦 h、横 w で hw 個の正方形のマスに区切られたボードを考えます。各マスには0
から9
の 1 桁の数字か、もしくは.
(ドット)が書かれています。また、ボードには、左上のマスが (1, 1)、右上が (1, w)、左下が (h, 1)、右下が (h, w) となるように、それぞれのマスに対して順に座標が振られています。
ボード内に書かれた整数が 1 つになるまで以下の手順を繰り返します。
-
整数が書かれたマスの組で、マンハッタン距離が最大になるような組の中から 1 つをランダムに選びます。(マンハッタン距離とは、2 つのマスの座標がそれぞれ (a, b)、(c, d) であるとき、|a - c| + |b - d| で計算される距離のことです)
-
1. で選んだ組において、マスに書かれた整数の和を元の数が大きいほうのマスに上書きし、小さいほうのマスには
.
を上書きします。もし元の数が等しい場合は、好きなほうに整数の和を上書きし、他方を.
で上書きします。
上記手順が終了した後、ボード内に残る可能性のある整数のうち、最大のものを求めてください。
入力
入力は以下の形式で与えられる。
h w b_1 ... b_h
- 1 行目には、ボードの縦と横の長さを表す整数 h, w (1 \leq h, w \leq 100) が与えられる。
- 続く h 行には、ボードの情報が与えられる。
- b_i はボードの上から i 行目の情報を表し、
0
から9
の 1 桁の整数もしくは.
を含む長さ w の文字列である。 - ボードは少なくとも 1 つの整数を含むことが保証される。
出力
ボードに残る可能性のある整数のうち最大のものを 1 行で出力せよ。
最後は改行し、余計な文字、空行を含まないこと。
入力例1
2 3 12. .5.
出力例1
8
入力例2
5 5 ..3.9 .1..6 2.3.4 7..11 ....8
出力例2
45