问题 28552 --Kakuro

28552: Kakuro

时间限制: 1 Sec  内存限制: 512 MB
提交: 1  解决: 1
[提交][状态][讨论版][数据上传:][下载FPS0元][下载测试数据0元][260kb]

题目描述

首先介绍一下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。

来源

[提交][状态]