1208: Kreuzsummen

Memory Limit:1024 MB Time Limit:5.000 S
Judge Style:Text Compare Creator:
Submit:1 Solved:1

Description

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

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


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


Input

Output

输出一个整数表示答案。

Sample Input Copy

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

Sample Output Copy

127

HINT

// 下面为这个样例的解释。
-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。

Source/Category