2300: Kreuzsummen
时间限制: 5Sec 内存限制:1024 MB提交:31 解决:11
[ 状态] [ 讨论版] [ 提交] [命题人: ]
题目描述
首先介绍一下Kakuro(カックロ) 这个游戏。
游戏规则为：
• 方形空格中填入1 ~ 9 的整数。
• 被斜线分开的方格中，右上角的数字等于其右侧邻接之连续方格
中数字之和，左下角的数字等于其下方邻接之连续方格中数字之
和。
• 无论是横向还是纵向，连续方格中的数字不能重复。
左边为一个Kakuro 游戏，右边为这个游戏的唯一解。
我们称一开始给出的数字为线索，称需要填入数字的地方为空格。如
果一个格子包含线索那么就不需要填入数字。我们约定所有的谜题都非空，
即至少有一个空格需要被填入。
注意：在以下题目中的游戏规则可能会有所不同，请认真阅读在每个
题目下的规则。
--------------------------------------------------------------------------------------------------------------------------------
输入
输出
输出一个整数表示答案。
样例输入
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
样例输出
Copy
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。