UOJ Logo

NOI.AC

#71. 作画鬼才

统计

【问题描述】

8012年,实验舱里诞生了一位沉迷作画的艺术家小Z。有一天他作了一张n行m列的像素画。每个像素位置上都有一个颜色,用小写字母来表示(最多s种颜色)。 有一天,不知道哪个淘气鬼给这张画创作了k个副本,每个副本都是在原来的像素画的基础上选取一个矩形并覆盖上了同一种新的颜色。 这让小Z突然萌生了将这新的k幅画出版成一个画册的冲动,于是乎他想选择一幅画作为封面,使得该封面与其他k-1幅画差异度之和最小。

定义差异度为:

$$dis(A,B)=\sum_{i=1}^n\ \sum_{j=1}^m\ \vert A_{i,j} - B_{i,j} \vert$$

于是乎你需要计算出以哪幅画为封面,差异度之和最小。以及这个最小差异度之和是多少。

【输入格式】

第一行为四个正整数 $n, m,k, s$。

接下来 $n$ 行,每行一个长度为 m 的字符串,表示原图。

接下来 $k$ 行,每行四个正整数和一个字符, $x1, y1, x2, y2, col$,表示以 $(x1, y1)$ 为左上⻆、$(x2, y2)$ 为右下⻆的矩形被涂成了 $col$ 这个颜色。

【输出格式】

输出一行两个整数,用空格隔开,依次表示最小的差距和封面的编号,若有多个答案,输出编号最小的。

【输入样例】

5 7 10 4
cbdadbd
bbccada
dacdabd
cdcacbc
baaddad
1 3 5 6 a
1 6 2 6 c
4 1 5 4 b
3 4 5 4 b
2 2 3 7 c
2 4 4 5 d
2 5 3 5 a
4 7 5 7 c
3 1 3 5 c
4 4 5 6 c

【输出样例】

85 7

【数据规模】

t3.jpg