← 返回题目列表

AtCoder · past23_o

O. 网格最大化

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

问题陈述

有一个网格 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