← 返回题目列表

Codeforces · 1517/D

D. 探索者空间

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

您正在2050年会议的探索空间中徘徊。

浏览器空间可以被视为大小为 $$$n\times m$$$ 的无向加权网格图。顶点集为 $$$\{(i, j)|1\le i\le n, 1\le j\le m\}$$$。当且仅当 $$$|i_1-i_2|+|j_1-j_2|=1$$$ 时,两个顶点 $$$(i_1,j_1)$$$ 和 $$$(i_2, j_2)$$$ 通过边连接。

在每一步中,您都可以走到由边与当前顶点连接的任何顶点。每条边缘都有一定数量的展品。由于您已经知道所有展品,因此每当您经过包含 $$$x$$$ 展品的边缘时,您的无聊感就会增加 $$$x$$$。

对于每个起始顶点 $$$(i, j)$$$,请回答以下问题:如果您从 $$$(i, j)$$$ 步行并在恰好 $$$k$$$ 步后返回到它,那么最小可能的无聊度是多少?

您可以多次使用任何边,但这些边上的无聊度也会被多次计数。在每一步中,您都不能停留在当前顶点。在穿过边缘时您也无法改变方向。在 $$$k$$$ 步骤后返回到起始顶点 $$$(i, j)$$$ 之前,您可以自由地访问 $$$(i, j)$$$ (或不)。

输入

第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$k$$$ ($$$2\leq n, m\leq 500, 1\leq k\leq 20$$$)。

以下 $$$n$$$ 行的第 $$$i$$$ 行中的第 $$$j$$$ 数字 ($$$1\le j \le m - 1$$$) 是顶点 $$$(i, j)$$$ 和顶点 $$$(i, j+1)$$$ 之间的边上的存在位数。

以下 $$$n-1$$$ 行的第 $$$i$$$ 行中的第 $$$j$$$ 个数字 ($$$1\le j\le m$$$) 是顶点 $$$(i, j)$$$ 和顶点 $$$(i+1, j)$$$ 之间的边上的存在位数。

每条边上的展品数量是 $$$1$$$ 和 $$$10^6$$$ 之间的整数。

输出

输出 $$$n$$$ 行,每行包含 $$$m$$$ 数字。如果您从 $$$(i, j)$$$ 开始,并在恰好 $$$k$$$ 步后返回,则第 $$$i$$$ 行中的第 $$$j$$$ 数字 $$$answer_{ij}$$$ 应该是可能的最小无聊度。

如果在 $$$k$$$ 步之后无法返回到顶点 $$$(i, j)$$$,则 $$$answer_{ij}$$$ 应为 $$$-1$$$。

示例

输入 #1

3 3 10
1 1
1 1
1 1
1 1 1
1 1 1

输出 #1

10 10 10
10 10 10
10 10 10

输入 #2

2 2 4
1
3
4 2

输出 #2

4 4
10 6

输入 #3

2 2 3
1
2
3 4

输出 #3

-1 -1
-1 -1

注意

在第一个示例中,无论您如何行走,答案始终是 $$$10$$$。

在第二个示例中,$$$answer_{21} = 10$$$,路径为 $$$(2,1) \to (1,1) \to (1,2) \to (2,2) \to (2,1)$$$,无聊度为 $$$4 + 1 + 2 + 3 = 10$$$。