Dungeons and Candies

题面翻译

题目描述

给定 $k$ 次文件，每次 $n*m$ 个字符。

传输文件，有两种方式：

1.直接传输，耗费 $n*m$ 个字符。

2.通过比较这个文件与前面某个文件的差别，耗费 $这个文件与那个文件不同的字符数*w$ 个字符，其中 $w$ 是常数。

文件顺序可任意交换。

求最小耗费字符数，并输出方案，有多种方案时任意输出一个。

输入格式

第一行，四个整数，$n,m,k,w$。

接下来 $n*k$ 行，每行 $m$ 个字符，表示 $k$ 个文件。

输出格式

第一行一个整数，最小花费。

接下来 $k$ 行，每行两个整数：

第一个整数表示这次输出的文件是第几个（因为传输顺序可以任意调换，所以这个是有必要的）。

第二个整数如果是 $0$，表示用了方法1；否则表示"那个文件"是第几个，即用了方法2。

数据范围

$1<=n,m<=10$

$1<=k,w<=1000$

字符只会是 '.' 或大小写字母。

题目描述

During the loading of the game "Dungeons and Candies" you are required to get descriptions of $k$ levels from the server. Each description is a map of an $n×m$ checkered rectangular field. Some cells of the field contain candies (each cell has at most one candy). An empty cell is denoted as "." on the map, but if a cell has a candy, it is denoted as a letter of the English alphabet. A level may contain identical candies, in this case the letters in the corresponding cells of the map will be the same.

When you transmit information via a network, you want to minimize traffic — the total size of the transferred data. The levels can be transmitted in any order. There are two ways to transmit the current level $A$ :

1. You can transmit the whole level $A$ . Then you need to transmit $n·m$ bytes via the network.
2. You can transmit the difference between level $A$ and some previously transmitted level $B$ (if it exists); this operation requires to transmit $d_{A,B}·w$ bytes, where $d_{A,B}$ is the number of cells of the field that are different for $A$ and $B$ , and $w$ is a constant. Note, that you should compare only the corresponding cells of levels $A$ and $B$ to calculate $d_{A,B}$ . You cannot transform the maps of levels, i.e. rotate or shift them relatively to each other.

Your task is to find a way to transfer all the $k$ levels and minimize the traffic.

输入格式

The first line contains four integers $n,m,k,w$ $(1<=n,m<=10; 1<=k,w<=1000)$ . Then follows the description of $k$ levels. Each level is described by $n$ lines, each line contains $m$ characters. Each character is either a letter of the English alphabet or a dot ("."). Please note that the case of the letters matters.

输出格式

In the first line print the required minimum number of transferred bytes.

Then print $k$ pairs of integers $x_{1},y_{1},x_{2},y_{2},...,x_{k},y_{k}$ , describing the way to transfer levels. Pair $x_{i}$ , $y_{i}$ means that level $x_{i}$ needs to be transferred by way $y_{i}$ . If $y_{i}$ equals 0, that means that the level must be transferred using the first way, otherwise $y_{i}$ must be equal to the number of a previously transferred level. It means that you will transfer the difference between levels $y_{i}$ and $x_{i}$ to transfer level $x_{i}$ . Print the pairs in the order of transferring levels. The levels are numbered 1 through $k$ in the order they follow in the input.

If there are multiple optimal solutions, you can print any of them.

样例 #1

样例输入 #1

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

样例输出 #1

14
1 0
2 1
3 1

样例 #2

样例输入 #2

1 1 4 1
A
.
B
.

样例输出 #2

3
1 0
2 0
4 2
3 0

样例 #3

样例输入 #3

1 3 5 2
ABA
BBB
BBA
BAB
ABB

样例输出 #3

11
1 0
3 1
2 3
4 2
5 1