问题 1635 --Kakuro

1635: Kakuro

时间限制: 1 Sec  内存限制: 512 MB
提交: 1  解决: 1
[提交][状态][讨论版][命题人:]

题目描述

首先介绍一下Kakuro(カックロ) 这个游戏。
游戏规则为：
• 方形空格中填入1 ~ 9 的整数。
• 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格
中数字之和，左下角的数字等于其下方邻接之连续方格中数字之
和。
• 无论是横向还是纵向，连续方格中的数字不能重复。


左边为一个Kakuro 游戏，右边为这个游戏的唯一解。
我们称一开始给出的数字为线索，称需要填入数字的地方为空格。如
果一个格子包含线索那么就不需要填入数字。我们约定所有的谜题都非空，
即至少有一个空格需要被填入。
注意：在以下题目中的游戏规则可能会有所不同，请认真阅读在每个
题目下的规则。
--------------------------------------------------------------------------------------------------------------------------------

游戏规则：

• 空格中填入正整数。
• 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格中数字之和，左下角的数字等于其下方邻
接之连续方格中数字之和。
Apia 给了Rimbaud 一个Kakuro 谜题。心不灵手不巧的Rimbaud 根本不会做Kakuro，所以只在空格里面
填上了一些随机的数字，称这个为一个局面，即包含了谜题一开始给出的线索和后面填入的数字。
现在Rimbaud 希望能修改这个局面使得她的答案是一个合法解。这个局面中有些数字(包括一开始的给出线
索和后面填入的数字) 是可以修改的。每个数字都有个特定的代价，将这个数字加1 或者减1 都得付出这个数字对
应的代价。注意对于一组合法解，必须满足游戏规则，也就是空格中填的数字必须是正整数并且满足和的条件，但
是不要求不重复。
Rimbaud 希望用最少的代价让这个局面变得合法，如果不可能那么输出-1。

输入

第一行，两个正整数表示n;m 表示这个游戏的行和列。
接下来n 行，每行包含m 个0 到4 的数字，第i 行第j 列表示第i 行第j 列格子的种类。
• 0 表示这个格子既不是空格也不是线索。
• 1 表示这个格子左下角包含线索，右上角没有线索。
• 2 表示这个格子右上角包含线索，左下角没有线索。
• 3 表示这个格子左下角右上角都包含线索。
• 4 表示这个格子为空格。
输入保证这个从格式上来说一定是个合法的Kakuro 谜题，即每一段连续的空格的左边或者上面的格子包含线
索。
接下来n 行，每行包含若干个正整数，按从左往右的顺序给出初始局面中的每个数字。特别地如果这个格子
的种类为3，那么先给出左下角的线索，再给出右上角的线索。
接下来n 行，每行包含若干个整数，按从左往右的顺序给出初始局面中的每个数字对应的代价。如果代价为
-1 表示这个格子不能修改，否则代价为非负整数。注意3 号格子的两个线索有着两个不同的代价。
样例1 给出了上面的谜题的输入，请在做题前阅读样例1 确保你理解了输入格式。

输出

一个整数表示最小的代价，如果不可能输出-1。

样例输入

8 8
0 1 1 0 0 1 1 1
2 4 4 0 3 4 4 4
2 4 4 3 4 4 4 4
2 4 4 4 4 4 1 0
0 2 4 4 3 4 4 1
0 1 3 4 4 4 4 4
2 4 4 4 4 2 4 4
2 4 4 4 0 2 4 4
23 30 27 12 16
16 9 7 17 24 8 7 9
17 8 9 15 29 8 9 5 7
35 6 8 5 9 7 12
7 6 1 7 8 2 6 7
11 10 16 4 6 1 3 2
21 8 9 3 1 5 1 4
6 3 1 2 3 2 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1

样例输出

0

提示

对于5% 的数据，保证所有的代价都为-1。

对于20% 的数据，保证所有空格中的数字代价都为-1。

对于另外30% 的数据，保证所有代表线索的数字的代价都为-1。

对于另外20% 的数据，保证只有第一行第一列包含线索，剩下的地方全都是空格。

对于100% 的数据，保证3 <= n;m <= 30，保证初始局面中的每个数字不超过10^6，保证每个数字的代价不超过

10^6。

来源

BJWC2018 高级 

[提交][状态]