问题 28553 --Kreuzsummen

28553: Kreuzsummen

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

题目描述

首先介绍一下Kakuro(カックロ) 这个游戏。

游戏规则为:
• 方形空格中填入1 ~ 9 的整数。
• 被斜线分开的方格中,右上角的数字等于其右侧邻接之连续方格
中数字之和,左下角的数字等于其下方邻接之连续方格中数字之
和。
• 无论是横向还是纵向,连续方格中的数字不能重复。


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


输入

输出

输出一个整数表示答案。

样例输入

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

样例输出

127

提示


// 下面为这个样例的解释。

-1 -1 -1 -1 -1 -1 -1 -1

-1 1 2 -1 -1 3 3 2

-1 2 2 -1 2 4 4 2

-1 3 4 1 2 5 -1 -1

-1 -1 1 5 -1 6 5 -1

-1 -1 -1 4 5 5 5 3

-1 8 8 5 6 -1 4 3

-1 2 3 3 -1 -1 2 2










数据范围






对于10% 的数据,保证n;m <= 3。


对于30% 的数据,保证n;m <= 50。

对于50% 的数据,保证n;m <= 500。

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

对于100% 的数据,保证3 <= n; m; T <= 10^5; 1 <= k <= 10^5; s <= 10^18。

来源

[提交][状态]