← 返回题目列表

AtCoder · code_festival_relay_e

E. 奇怪的添加

中文机器翻译题面 查看原题

問題文

縦 h、横 w 考虑一块分为 hw 方形单元的板。在每个方格内0不同编号的点最多为9的 1 数字或 写入.(点)。另外,在棋盘上,左上角的方块是 (1, 1),右上角是 (1, w),左下角是 (h, 1),右下是 坐标按顺序分配给每个方格,以便 (h, w) 。


黑板上写的整数是 1 重复这些步骤,直到获得一个。

  1. 在写入整数的方格集合中,从具有最大曼哈顿距离的集合中进行选择。 1 随机选择一个。 (曼哈顿距离是多少?2 每个方块的坐标是 当 (a, b)、(c, d) 时,|a - c| + |b - d| 是计算出的距离)

  2. 1. 对于步骤 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