loj#P3141. 「BJWC2018」Kakuro

「BJWC2018」Kakuro

题目描述

题目背景

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

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

冬令营I试_2_1.png冬令营I试_2_2.png

左边为一个 Kakuro 游戏,右边为这个游戏的唯一解。

我们称一开始给出的数字为线索,称需要填入数字的地方为空格。如果一个格子包含线索那么就不需要填入数字。我们约定所有的谜题都非空,即至少有一个空格需要被填入。

注意:在以下题目中的游戏规则可能会有所不同,请认真阅读在每个题目下的规则。

题目详情

游戏规则:

  • 空格中填入正整数。
  • 被斜线分开的方格中,右上角的数字等于其右侧邻接之连续方格中数字之和,左下角的数字等于其下方邻 接之连续方格中数字之和。

Apia 给了 Rimbaud 一个 Kakuro 谜题。心不灵手不巧的 Rimbaud 根本不会做 Kakuro,所以只在空格里面填上了一些随机的数字,称这个为一个局面,即包含了谜题一开始给出的线索和后面填入的数字。现在 Rimbaud 希望能修改这个局面使得她的答案是一个合法解。这个局面中有些数字(包括一开始的给出线索和后面填入的数字)是可以修改的。每个数字都有个特定的代价,将这个数字加 11 或者减 11 都得付出这个数字对应的代价。注意对于一组合法解,必须满足游戏规则,也就是空格中填的数字必须是正整数并且满足和的条件,但是不要求不重复。

Rimbaud 希望用最少的代价让这个局面变得合法,如果不可能那么输出 1-1

输入格式

第一行,两个正整数表示 n,mn,m 表示这个游戏的行和列。

接下来 nn 行,每行包含 mm0044 的数字,第 ii 行第 jj 列表示第 ii 行第 jj 列格子的种类。

  • 00 表示这个格子既不是空格也不是线索。
  • 11 表示这个格子左下角包含线索,右上角没有线索。
  • 22 表示这个格子右上角包含线索,左下角没有线索。
  • 33 表示这个格子左下角右上角都包含线索。
  • 44 表示这个格子为空格。

输入保证这个从格式上来说一定是个合法的 Kakuro 谜题,即每一段连续的空格的左边或者上面的格子包含线索。

接下来 nn 行,每行包含若干个正整数,按从左往右的顺序给出初始局面中的每个数字。特别地如果这个格子的种类为 33,那么先给出左下角的线索,再给出右上角的线索。

接下来 nn 行,每行包含若干个整数,按从左往右的顺序给出初始局面中的每个数字对应的代价。如果代价为 1-1 表示这个格子不能修改,否则代价为非负整数。注意 33 号格子的两个线索有着两个不同的代价。

输出格式

一个整数表示最小的代价,如果不可能输出 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 5
0 1 1 1 1
2 4 4 4 4
2 4 4 3 4
2 4 4 4 4
2 4 4 4 4
16 8 6 8
4 4 9 5 4
12 8 4 19 10 4
14 2 3 3 6
1 7 9 4 5
17 5 10 13
11 15 16 4 14
20 20 15 5 16 3
4 3 19 2 4
19 19 13 15 20
822

数据范围与提示

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

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

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

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

对于 100%100\% 的数据,保证 3n,m303\le n, m\le 30,保证初始局面中的每个数字不超过 10610^6,保证每个数字的代价不超过 10610^6