J12 习题-4 灯泡游戏

题目描述

有一个 $n$ 行 $m$ 列的矩阵，左上角坐标是 $(0,0)$，右下角坐标是 $(n-1,m-1)$。每个格子有一个字符，“0”至“9”表示数字 $0$ 至 $9$，“a”至“z”表示数字 $10$ 至$35$，“A”至“Z”表示数字 $36$ 至 $61$。矩阵的每个格子都有一个灯泡，刚开始除了左上角的灯泡是亮的，其他的灯泡都是灭的，刚开始你的得分是 $0$。 游戏的过程是这样的：每次选一个灯泡是亮的格子 $X$ ，同时选一个灯泡是灭的格子 $Y$，而且要求格子 $X$ 和格子 $Y$ 是相邻(上、下、左、右)的格子。这个步骤会使你的得分增加，增加的值是：格子 $X$ 与格子 $Y$ 代表的数字的差的绝对值。当然，这个步骤会使你选中的灭的灯泡变亮。重复上述操作，直到所有的灯泡都变成亮的。问你的最大得分是多少？

输入格式

第 $1$ 行：两个整数 $n$ 和 $m$。 接下来是 $n$行 $m$ 列的矩阵。

输出格式

一个整数，表示最大得分。

输入样例

2 2
05
aB

输出样例

69

样例说明

第一次选择：格子 $(0,0)$ 和格子 $(1，0)$，得分是 $10-0=10$；第二次选择：格子 $(1,0)$ 和格子 $(1,1)$，得分是 $37-10=27$；第三次选择：格子 $(1,1)$和格子 $(0,1)$，得分是 $37-5=32$，因此总得分是：$10+27+32=69$。

数据范围

对于$100\%$的数据，保证 $1\leq n,m \leq 50$；