问题陈述
有一个网格 H 水平行和 W 垂直列。
行中的单元格 i (从顶部算起)和列 j (从左边开始)上面写着 A_{i,j} 如果 A_{i,j}\neq -1,如果 A_{i,j}=-1.
在这里, A_{i,j} 是介于 -1 和 9.
你将写一个介于 0 和 9之间的整数(包括两端)到每个空格中,使得:
- 对于任何共享边的两格,写在两个格子上的数字之和为 D 或更少。
找出新写入数字的可能最大总和。
约束
- 1 \leq H,W \leq 15
- 0 \leq D \leq 18
- -1 \leq A_{i,j} \leq 9
- 所有输入值均为整数。
- 存在一种符合条件的数字分配。
输入
输入由标准输入按以下格式给出:
H W D
A_{1,1} A_{1,2} \ldots A_{1,W}
A_{2,1} A_{2,2} \ldots A_{2,W}
\vdots
A_{H,1} A_{H,2} \ldots A_{H,W}
输出
打印答案。
示例输入 1
2 3 10 5 -1 3 2 4 -1
示例输出 1
11
通过写 5 写在行 1 和专栏 2,和 6 写在行 2 和专栏 3的格子,新写入的数字总和为 11,且任何相邻格子之和为 10 或更少。
这是最大的,因为无法使新写入数字的总和 12 或更大。
示例输入 2
2 1 18 -1 0
示例输出 2
9
注意我们只能写介于 0 和 9.
示例输入 3
3 2 10 4 4 4 4 4 4
示例输出 3
0
之间的整数。 可能没有空格。
示例输入 4
8 9 6 2 -1 3 -1 3 2 3 -1 3 -1 2 2 3 -1 3 -1 3 2 -1 3 -1 -1 3 2 3 2 -1 -1 -1 -1 2 2 3 2 -1 2 -1 3 1 -1 -1 2 3 2 2 -1 -1 -1 1 4 1 -1 -1 3 3 -1 -1 4 1 2 -1 -1 2 2 -1 -1 1 -1 -1 2 2 1
示例输出 4
91