← 返回题目列表

Codeforces · 436/C

C. 地下城与糖果

中文机器翻译题面 查看原题

在加载游戏“地下城与糖果”期间,您需要从服务器获取 k 个关卡的描述。每个描述都是一个 n × m 方格矩形区域的地图。场地中的某些单元格包含糖果(每个单元格最多有一颗糖果)。空单元格表示为“.”。在地图上,但如果一个单元格有糖果,它就会被表示为英文字母表中的字母。一个关卡可能包含相同的糖果,在这种情况下,地图相应单元格中的字母将相同。

当您通过网络传输信息时,您希望最小化流量——传输数据的总大小。电平可以按任何顺序传输。传输当前电平A有两种方式:

1、可以传输整个A级,那么需要通过网络传输n·m个字节。
2.您可以传输级别A与某些先前传输的级别B之间的差异(如果存在);该操作需要传输dA, B·w字节,其中dA, B是A和B不同的字段单元数,w是常数。请注意,您应该仅比较级别 A 和 B 的相应单元格来计算 dA, B。您不能变换级别的地图,即旋转或相对于彼此移动它们。

你的任务是找到一种方法来传输所有 k 个级别并最小化流量。

输入

第一行包含四个整数 n、m、k、w(1 ≤ n,m ≤ 10;1 ≤ k,w ≤ 1000)。接下来是k个级别的描述。每个级别由n行描述,每行包含m个字符。每个字符可以是英文字母表中的字母或点(“.”)。请注意字母的大小写很重要。

输出

在第一行中打印所需的最小传输字节数。

然后打印k对整数x1, y1, x2, y2, ..., xk, yk,描述转移级别的方式。 xi,yi 配对表示xi 层需要通过yi 方式转移。如果 yi 等于 0,则表示该级别必须使用第一种方式转移,否则 yi 必须等于先前转移的级别号。这意味着您将传递 yi 级和 xi 级之间的差值来传递 xi 级。按照传输级别的顺序打印对。级别按照它们在输入中遵循的顺序编号为 1 到 k。

如果有多个最优解,可以打印任意一个。

示例

输入 #1

2 3 3 2
A.A
...
A.a
..C
X.Y
...

输出 #1

14
1 0
2 1
3 1

输入 #2

1 1 4 1
A
.
B
.

输出 #2

3
1 0
2 0
4 2
3 0

输入 #3

1 3 5 2
ABA
BBB
BBA
BAB
ABB

输出 #3

11
1 0
3 1
2 3
4 2
5 1